並べ替え順に配列のすべての順列を生成する方法は？

Question

私は配列を持っており、ユーザーは文字列を挿入できます。

そして、私はこのコードを持っている：

int main(){ 
    char anagrama[13]; 
    cin >> anagrama; 
    for(int j = 0; j < strlen(anagrama); j++){ 
    cout << anagrama[j]; 
    for(int k = 0; k < strlen(anagrama); k++){ 
     if(j != k) 
     cout << anagrama[k]; 
    } 
    cout << endl; 
    } 
} 

問題は、私はすべての順列内の文字列のが順番を並べ替える必要があるということです。例えば

ユーザーの書き込み場合：abc、出力が可能にする必要があります。

abc 
acb 
bac 
bca 
cab 
cba 

と私のコードは

をソートされたすべての順列を示し、いないいないあなたは私を助けることができますか？

機能が実装されていない実装を行う必要があります。

私は再帰関数と思うが、私はどのようにわからない。

これは一例です：繰り返しのない http://www.disfrutalasmatematicas.com/combinatoria/combinaciones-permutaciones-calculadora.html、あなたが1で順列の1を通過するstd::next_permutationを使用することができますC++では

Answer 1

をソート。あなたは初めてstd::next_permutationを呼び出す前に、アルファベット順に文字をソートする必要があります。ここでは

cin>>anagrama; 
int len = strlen(anagrama); 
sort(anagrama, anagrama+len); 
do { 
    cout << anagrama << endl; 
} while (next_permutation(anagrama, anagrama+len)); 

はdemo on ideoneです。

自分で順列を実装する必要がある場合は、borrow the source codeをnext_permutationにするか、順列アルゴリズムを再帰的に実装する簡単な方法を選択します。

Answer 2

#include <iostream> 
#include <string> 
#include <algorithm> 

using namespace std; 

void permute(string select, string remain){ 
    if(remain == ""){ 
     cout << select << endl; 
     return; 
    } 
    for(int i=0;remain[i];++i){ 
     string wk(remain); 
     permute(select + remain[i], wk.erase(i, 1)); 
    } 
} 

int main(){ 
    string anagrama; 
    cout << "input character set >"; 
    cin >> anagrama; 
    sort(anagrama.begin(), anagrama.end()); 
    permute("", anagrama); 
} 

---

別のバージョン

#include <iostream> 
#include <string> 
#include <vector> 
#include <iterator> 
#include <algorithm> 

using namespace std; 

void permute(string& list, int level, vector<string>& v){ 
    if(level == list.size()){ 
     v.push_back(list); 
     return; 
    } 
    for(int i=level;list[i];++i){ 
     swap(list[level], list[i]); 
     permute(list, level + 1, v); 
     swap(list[level], list[i]); 
    } 
} 

int main(){ 
    string anagrama; 
    vector<string> v; 
    cout << "input character set >"; 
    cin >> anagrama; 
    permute(anagrama, 0, v); 
    sort(v.begin(), v.end()); 
    copy(v.begin(), v.end(), ostream_iterator<string>(cout, "\n")); 
} 

Answer 3

私はすでにでも任意のテンプレートとコンテナを実装する機能のないものを書きました。実際にはC言語で書かれていますが、C++に変換されています。

わかりやすく効率が悪く、その出力はソートされたものです。

#include <iostream> 
#define N 4 
using namespace std; 

char ch[] = "abcd"; 

int func(int n) { 
    int i,j; 
    char temp; 
    if(n==0) { 
     for(j=N-1;j>=0;j--) 
      cout<<ch[j]; 
     cout<<endl; 
     return 0; 
    } 
    for(i=0;i<n;i++){ 
     temp = ch[i]; 
     for(j=i+1;j<n;j++) 
      ch[j-1] = ch[j]; 
     ch[n-1] = temp; 
     //shift 
     func(n-1); 
     for(j=n-1;j>i;j--) 
      ch[j] = ch[j-1]; 
     ch[i] = temp; 
     //and shift back agian 
    } 
    return 1; 
} 

int main(void) 
{ 
    func(N); 
    return 0; 
} 

Answer 4

/*Think of this as a tree. The depth of the tree is same as the length of string. 
In this code, I am starting from root node " " with level -1. It has as many children as the characters in string. From there onwards, I am pushing all the string characters in stack. 
Algo is like this: 

1. Put root node in stack. 
2. Loop till stack is empty 
2.a If backtracking 
2.a.1 loop from last of the string character to present depth or level and reconfigure datastruture. 
2.b Enter the present char from stack into output char 

2.c If this is leaf node, print output and continue with backtracking on. 
2.d Else find all the neighbors or children of this node and put it them on stack. */ 



     class StringEnumerator 
     { 
     char* m_string; 
     int m_length; 
     int m_nextItr; 
     public: 
     StringEnumerator(char* str, int length): m_string(new char[length + 1]), m_length(length) , m_Complete(m_length, false) 
     { 
     memcpy(m_string, str, length); 
     m_string[length] = 0; 
     } 
    StringEnumerator(const char* str, int length): m_string(new char[length + 1]), m_length(length) , m_Complete(m_length, false) 
    { 
     memcpy(m_string, str, length); 
     m_string[length] = 0; 
    } 
    ~StringEnumerator() 
    { 
     delete []m_string; 
    } 

    void Enumerate(); 
    }; 


     const int MAX_STR_LEN = 1024; 
     const int BEGIN_CHAR = 0; 

     struct StackElem 
     { 
     char Elem; 
     int Level; 
     StackElem(): Level(0), Elem(0){} 
     StackElem(char elem, int level): Elem(elem), Level(level){} 

     }; 

     struct CharNode 
     { 
     int Max; 
     int Curr; 
     int Itr; 
     CharNode(int max = 0): Max(max), Curr(0), Itr(0){} 
     bool IsAvailable(){return (Max > Curr);} 
     void Increase() 
     { 
     if(Curr < Max) 
      Curr++; 
     } 
     void Decrease() 
     { 
     if(Curr > 0) 
      Curr--; 
     } 
     void PrepareItr() 
     { 
     Itr = Curr; 
     } 
}; 




     void StringEnumerator::Enumerate() 
{ 

    stack<StackElem> CStack; 
    int count = 0; 
    CStack.push(StackElem(BEGIN_CHAR,-1)); 
    char answerStr[MAX_STR_LEN]; 
    memset(answerStr, 0, MAX_STR_LEN); 

    bool forwardPath = true; 

    typedef std::map<char, CharNode> CharMap; 

    typedef CharMap::iterator CharItr; 
    typedef std::pair<char, CharNode> CharPair; 

    CharMap mCharMap; 
    CharItr itr; 

    //Prepare Char Map 
    for(int i = 0; i < m_length; i++) 
    { 
     itr = mCharMap.find(m_string[i]); 
     if(itr != mCharMap.end()) 
     { 
      itr->second.Max++; 
     } 
     else 
     { 
      mCharMap.insert(CharPair(m_string[i], CharNode(1))); 
     } 
    } 


    while(CStack.size() > 0) 
    { 
     StackElem elem = CStack.top(); 
     CStack.pop(); 

     if(elem.Level != -1)  // No root node 
     { 
      int currl = m_length - 1; 
      if(!forwardPath) 
      { 
       while(currl >= elem.Level) 
       { 
        itr = mCharMap.find(answerStr[currl]); 
        if((itr != mCharMap.end())) 
        { 
         itr->second.Decrease(); 
        } 
        currl--; 
       } 

       forwardPath = true; 
      } 

      answerStr[elem.Level] = elem.Elem; 

      itr = mCharMap.find(elem.Elem); 
      if((itr != mCharMap.end())) 
      { 
       itr->second.Increase(); 
      } 
     } 

     //If leaf node 
     if(elem.Level == (m_length - 1)) 
     { 
      count++; 
      cout<<count<<endl; 
      cout<<answerStr<<endl; 
      forwardPath = false; 
      continue; 
     } 

     itr = mCharMap.begin(); 

     while(itr != mCharMap.end()) 
     { 
      itr->second.PrepareItr(); 
      itr++; 
     } 


     //Find neighbors of this elem 
     for(int i = 0; i < m_length; i++) 
     { 
      itr = mCharMap.find(m_string[i]); 
      if(/*(itr != mCharMap.end()) &&*/ (itr->second.Itr < itr->second.Max)) 
      { 
       CStack.push(StackElem(m_string[i], elem.Level + 1)); 
       itr->second.Itr++; 
      } 
     } 


    } 


} 

Answer 5

このプログラムの出力@alexanderあなたが要求したとして、正確な順序である：HERE

、いくつかの特別なを含めずに指定された配列の全ての組み合わせ/順列を生成するための最も簡単なコードです。 （iostream.hと文字列が含まれています）、通常より特別な名前空間を使用しません（名前空間stdのみが使用されます）。

void shuffle_string_algo(string ark) 
{ 

//generating multi-dimentional array: 

char** alpha = new char*[ark.length()]; 
for (int i = 0; i < ark.length(); i++) 
    alpha[i] = new char[ark.length()]; 

//populating given string combinations over multi-dimentional array 
for (int i = 0; i < ark.length(); i++) 
    for (int j = 0; j < ark.length(); j++) 
     for (int n = 0; n < ark.length(); n++) 
      if((j+n) <= 2 * (ark.length() -1)) 
       if(i == j-n) 
        alpha[i][j] = ark[n]; 
       else if((i-n)== j) 
        alpha[i][j] = ark[ ark.length() - n]; 

if(ark.length()>=2) 
{ 
    for(int i=0; i<ark.length() ; i++) 
    { 
     char* shuffle_this_also = new char(ark.length()); 
     int j=0; 
     //storing first digit in golobal array ma 
     ma[v] = alpha[i][j]; 

     //getting the remaning string 
     for (; j < ark.length(); j++) 
      if((j+1)<ark.length()) 
       shuffle_this_also[j] = alpha[i][j+1]; 
      else 
       break; 
     shuffle_this_also[j]='\0'; 

     //converting to string 
     string send_this(shuffle_this_also); 

     //checking if further combinations exist or not 
     if(send_this.length()>=2) 
     { 
      //review the logic to get the working idea of v++ and v-- 
      v++; 
      shuffle_string_algo(send_this); 
      v--; 
     } 
     else 
     { 
      //if, further combinations are not possiable print these combinations 
      ma[v] = alpha[i][0]; 
      ma[++v] = alpha[i][1]; 
      ma[++v] = '\0'; 
      v=v-2; 

      string disply(ma); 
      cout<<++permutaioning<<":\t"<<disply<<endl; 
     } 
    } 
} 
} 

とメイン：

int main() 
{ 
string a; 
int ch; 
do 
{ 
    system("CLS"); 
    cout<<"PERMUNATING BY ARK's ALGORITH"<<endl; 
    cout<<"Enter string: "; 
    fflush(stdin); 
    getline(cin, a); 

    ma = new char[a.length()]; 

    shuffle_string_algo(a); 

    cout<<"Do you want another Permutation?? (1/0): "; 
    cin>>ch; 
} while (ch!=0); 

return 0; 
} 

HOPE！それはあなたを助ける！論理を理解することに問題がある場合は、以下でコメントして編集します。