1

問題が発生しています。アルファベットの 26 文字のすべての可能な組み合わせを反復処理したい (うーん.... 25 文字だけ、「q」を除外したい)。簡単そうに見えて、なかなか難しい。q を除く az を含む 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

2文字の単語、次に3文字、次に4文字のすべての組み合わせを考え出し、残りのアルファベットのあとがきを追加します. 残りのアルファベットを追加するコードがあるので、必要なのは最初の部分だけです。

n文字の単語を生成する方法を見つけた後、繰り返しが発生します。2文字の単語ごとに繰り返すと、「ab ac ad ... az ba bc bd .. bz」が得られますが、最後にabcdef..zを追加したことを思い出してください（使用済みの文字を除く）ので、実際には「abcd. .z acbde..z adbcef..z" など。2 文字の単語 ab と 3 文字の単語 abc は重複しており、これは大きなキーワードでは非効率的です。

4

2 に答える 2

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 に答える
1

バックトラックのアイデアを使用して開始できます。しかし、25を生成します！大変な作業です。通常のコンピューターでは、このような大規模な検索スペースを反復処理するには、かなりの時間がかかります (つまり、かなりの時間を要します)。目的の出力で絶対に発生しないと確信しているようなケースを考えて、検索スペースを PRUNE するようにしてください。刈り込みによるバックトラッキングと呼ばれる手法を探す必要があります。

于 2013-07-30T14:07:14.653 に答える