如何按排序順序生成數組的所有排列？

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沒有重複和分類

Answer 1

在C++中，你可以使用std::next_permutation通過一個經過排列之一。您需要按字母順序調用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該程序的輸出是在確切順序的要求由你：

在這裏，是用於生成所有組合的最簡單的代碼/給定陣列的排列，而不包括一些特殊的庫（僅包含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; 
} 

希望！它可以幫助你！如果您在理解邏輯時遇到問題，請在下面評論，我會編輯。