c++ - 非重复排列

Question

我有一个问题。我想遍历字母表中 26 个字母的所有可能组合(好吧......只有 25 个字母，我想排除'q')。看似简单，实则困难重重。我想从一个包含 a-z(不包括 q)的 char* 开始，还有一个 for 循环，它将遍历这些字母的所有可能组合(顺序很重要，没有重复的字母)，执行一个函数来检查该组合是否是我正在寻找。

std::next_permutation 不适用于我的场景。具体来说，我需要将向后迭代的代码。从...开始:一个 bcd .... z,b acde .... z,c abde .... z,...z abcd .... y,

ab cdef.... z,交流 bdef .... z,广告
..z

吧公元前

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

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

Answer 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;
}