1

我有一个问题。我想遍历字母表中 26 个字母的所有可能组合（嗯......只有 25 个字母，我想排除 'q'）。这看起来很简单，但事实证明很难。我想从一个包含 az 不包括 q 的 char* 开始，以及一个 for 循环，它将遍历这些字母的所有可能组合（顺序很重要，没有重复的字母），执行一个检查该组合是否是我的函数寻找。

std::next_permutation 不适用于我的场景。具体来说，我需要能够向后迭代的代码。开头：a bcd.... z, b acde.... z, c abde.... z, ... z abcd.... y,

ab cdef.. z, ac bdef.. z, ad
.. az

ba bc bd

几乎想出两个字母单词的每个组合，然后是三个字母，然后是四个字母，然后添加其余的字母表。我有添加其余字母的代码，所以我只需要第一部分。

在我弄清楚如何生成 n 个字母的单词之后，它会导致重复。遍历每两个字母的单词，我得到“ab ac ad ... az ba bc bd .. bz”，但请记住我将 abcdef..z 添加到它的末尾（不包括用完的字母），所以它实际上是“abcd. .z acbde..z adbcef..z" 等。两个字母词ab和三个字母词abc重叠，对于较大的关键字效率低下。

4

2 回答 2

1

您可以使用回溯的想法开始。但是生成25！是一项艰巨的任务。对于普通计算机而言，遍历如此大的搜索空间将花费很多（我真的是说很多）。您应该尝试通过考虑您确信它永远不会出现在所需输出中的情况来修剪您的搜索空间。您应该寻找一种称为带有修剪的回溯的技术。

于 2013-07-30T14:07:14.653 回答
1

试试这个。我通常避免递归，但在这里效果很好：

#include <vector>
#include <set>
#include <iostream>
#include <algorithm>

using std::vector;
using std::cout;
using std::endl;
using std::find;

void printVec(vector<char> &vec)
{
    for(int i = 0; i < vec.size(); i++)
    {
        cout << vec[i];
    }
    cout << endl;
}

void incrementCharAvoidingDuplicates(vector<char> v, char &c)
{
    // increment newChar until we find one not in the vector already
    while(std::find(v.begin(), v.end(), c)!=v.end())
    {
        c++;
    }
}

bool incrementVec(vector<char> &v)
{
    if(v.size() == 0 || v.size() >= 25)
            return false;

    //try incrementing the final character
    char newChar = v.back() + 1;

    incrementCharAvoidingDuplicates(v, newChar);

    // if it's still in range, we have succesfully incremented the vector
    if(newChar <= 'z')
    {
        v.back() = newChar;

        return true;
    }
    // if not (e.g. "abz") then remove the final character and try to increment the base part instead
    else
    {
        vector<char> w(v.begin(), v.end() - 1);

        if(incrementVec(w))
        {
            // we succeeded in incrementing the base ... so find a remaining character that doesn't conflict and append it
            // (note there will always be one since we insisted size < 25)
            v.resize(w.size());
            std::copy(w.begin(), w.end(), v.begin());

            char newChar = 'a';

            incrementCharAvoidingDuplicates(v, newChar);

            v.push_back(newChar);

            return true;
        }
        // otherwise we could not increment the final char, could not increment the base...so we are done
        else
        {
            return false;
        }
    }
}

int main()
{
    static const char arr[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','r','s','t','u','v','w','x','y','z'};
    vector<char> originalAlphabet (arr, arr + sizeof(arr) / sizeof(arr[0]) );
    vector<char> currentWord;
    int desiredWordLength;

    for(desiredWordLength = 1; desiredWordLength < 25; desiredWordLength++)
    {
        currentWord.clear();

        //build first list e.g. a, abc, abcdef, ...
        for(int j = 0; j < desiredWordLength; j++)
        {
            currentWord.push_back(originalAlphabet[j]);
        }

        do{
            printVec(currentWord);
        } while( incrementVec(currentWord));

    }

    return 0;
}
于 2013-07-31T08:40:43.227 回答