配列内の文字の順列

Question

文字配列を入力し、その配列のすべての可能な組み合わせを出力として取得したいとします。例えば 、I入力文字列= 'B、C'、 私はこの形式で出力したい場合：

a b c, 
a c b, 
b a c, 
b c a, 
c a b, 
c b a 

と同様に、私が取得したいI入力4文字の場合を24種類の組み合わせがあります。これに対してコードを作成しましたが、入力文字の2倍の組み合わせしか返しません。つまり、コードは3文字を入力すると6個の組み合わせが返されますが、4文字を入力すると24個の組み合わせではなく8個の組み合わせしか返されません。用語について

#include <iostream> 
#include<string.h> 
#include<stdio.h> 
using std::cout; 
void getCombination(char *); 

int main() 
{ 
    const int maxStringSize = 26; 
    char thisString[maxStringSize]; 
    cout<<"Enter String = "; 
    gets (thisString); 
    getCombination(thisString); 
    return 0; 
} 

void getCombination(char *thisString) 
{ 
    int stringSize=strlen(thisString); 
    for(int i = 0; i<stringSize; i++) 
    { 
     for(int j = 0; j<stringSize; j++) 
     { 
      cout<<thisString[(i+j)%stringSize]; 
     } 
     cout<<"\n"; 
     for(int k = stringSize-1; k>=0; k--) 
     { 
      cout<<thisString[(i+k)%stringSize]; 
     } 
    cout<<"\n"; 
    } 
} 

Answer 1

コメント：次のように 私のコードは、これらの順列組み合わせではないと呼ばれています。あなただけで形成されている順列を見ているためだ

：

ために、残りを入れて最初の文字と

を選ぶ

• または、
• 逆順
に休息を入れ

特にacbdをこのようにしてabcdから作成することはできません。

代わりに最初のパスとして再帰的な解決策を試すことをお勧めします（最初の文字を選んで残りのすべての並べ替えを見てください）。

再帰的なソリューションから、あまりにも多くの再帰呼び出しに起因するスタックオーバーフローが心配な場合は、スタックのようなデータ構造を使用するソリューションを作成できます。

Answer 2

http://www.sgi.com/tech/stl/next_permutation.html

のstd :: next_permutationはあなたのコードが失敗したなぜあなたは

Answer 3

を行くのを助ける必要がありますか？

あなたのコードは、それがあなたがやっていることであるため、2回の順列を生成します。接頭辞を選択してから、文字列を順番に、逆の順序で印刷します。つまり、接頭辞ごとに2つの出力があります。総数= n * 2。 （この方法ですべての順列をどのように印刷することができますか？）

解決策！

必要なものは、std :: next_permutationです。 next_permutationで配列を渡す前に配列をソートすることを忘れないでください。順序が変わる順番に配列が生成されます。

正しい出力を生成する再帰的な実装とnext_permutationの実装方法については、C++ hereを参照してください。

Answer 4

私はそれがこの方法を行うことができると思います：

void swap(char &a, char &b) { 
char c=a; 
a = b; 
b = c; 
} 


void get_Combination(string word, int d) { 
if (d == word.size()) { 
    cout<<word<<endl; 
    return; 
} 

for (int i=d; i< word.size(); ++i) { 
    swap(word[i],word[d]); 
    get_combination(word, d+1); 
    swap(word[i],word[d]); 
} 
} 

は説明： Uはget_combination（ワード、0）を呼び出すことによって開始します。文字列のすべての順列を見つけるために、各位置の各文字は、1つまたは他の順列の最初の位置に現れるはずです。したがって、d = 0で始まり、文字がdの文字列の終わりまですべての文字を入れ替えます。最初の文字をそのまま使用して、get_combination（word、d + 1）を呼び出すことで2番目の文字から始まるプロセスを繰り返します。最初にスワップされた文字を元の場所に戻し、次の文字をdの文字と入れ替えるために必要な2番目のスワップにも注意してください。

例：文字列abcを考える

、ここでは、標準ライブラリのアルゴリズムの一部でstd::next_permutationを使用してそれを行うことができます再帰ツリー、GC = get_combination

gc("abc",0) 

    gc(abc,1) 

     gc(abc,2) 

     cout<<"abc" 

     gc(acb,2) 

     cout<<"acb" 

    gc(bac,1) 

     gc(bac,2) 

     cout<<"bac" 

     gc(bca,2) 

     cout<<"bca" 

    gc(cba,1) 

     gc(cba,2) 

     cout<<"cba" 

     gc(cab,2) 

     cout<<"cab" 

Answer 5

です。以下のコードスニペットを参考にしてください。すべての組み合わせを見つけるにはnext_permutationが必要であるため、最初にtheStringをソートすることに注意してください。

#include <iostream> 
#include <algorithm> 

int main() 
{ 
    std::string theString = "abc"; 

    std::sort(theString.begin(), theString.end()); 

    do 
    { 
     std::cout << theString << std::endl; 
    } 
    while (std::next_permutation(theString.begin(), theString.end())); 

    return 0; 
}