1

指定された文字列の可能なすべての組み合わせを辞書順に生成するコードを作成しようとしました。

私が書いたコードは次のとおりです。

void get(char *n)
 {
    int l=strlen(n); 
    sort(n,n+l);
    int k=0,m,i,j,z;

    while(k<l)
    {
        m=k;

        for(i=k;i<l;i++)
        {
            for(j=k;j<=i;j++)
                cout<<n[j];

            cout<<"\n";
        }

        for(z=m+2;z<l;z++)
            cout<<n[m]<<n[z]<<"\n";  

        k++;
    }
 }


int main() 
 {
    char n[100];
    cin>>n;
    get(n);
    return 0;
 }

文字列が abcde であるとします。

私のコードは次のような組み合わせを生成していません:

abd
abe

文字列 abcde の出力は次のとおりです。

a 
ab
abc 
abcd 
abcde 
ac 
ad
ae 
b 
bc 
bcd 
bcde 
bd 
be 
c 
cd 
cde 
ce 
d 
de 
e

出力に次のような文字列が含まれていません。abd abe

これで質問が明確になることを願っています

効率的なアルゴリズムを使用してこれらすべての組み合わせを生成する方法

4

2 に答える 2

2

これは単純な再帰的アプローチです。

#include <string>
#include <iostream>
using namespace std;

void get( string str, string res ) {

   cout << res << endl;

   for( int i = 0; i < str.length(); i++ )
      get( string(str).erase(i,1), res + str[i] );
}

int main( int argc, char **argv) {

   string str = "abcde";
   get( str, "" );  
   return 0;
}

最も効率的な方法ではないかもしれませんが、短くて簡単な方法です。とにかく、すべての組み合わせを列挙するとO(2 n )の複雑さがあることに注意してください。したがって、効率的なアルゴリズムはまったく存在しません。

于 2015-03-15T11:20:25.930 に答える