Come generare tutte le permutazioni di un array in ordine ordinato?

Ho una matrice e l’utente può inserire una stringa.

E ho questo codice:

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; } } 

Il problema è che ho bisogno di tutte le permutazioni della stringa in ordine ordinato .

Ad esempio se l’utente scrive: abc , l’output deve essere:

 abc acb bac bca cab cba 

e il mio codice non mostra tutte le permutazioni e non è ordinato

Mi potete aiutare?

Ho bisogno di fare l’implementazione senza una funzione già implementata.

Penso con una funzione ricorsiva, ma non so come.

Questo è un esempio: http://www.disfrutalasmatematicas.com/combinatoria/combinaciones-permutaciones-calculadora.html senza ripetizione e ordinato

In C ++ puoi usare std::next_permutation per passare attraverso le permutazioni una per una. È necessario ordinare i caratteri in ordine alfabetico prima di chiamare std::next_permutation per la prima volta:

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

Ecco una demo su ideone .

Se è necessario implementare le permutazioni da soli, è ansible prendere in prestito il codice sorgente di next_permutation o scegliere un modo più semplice di implementare un algoritmo di permutazione in modo ricorsivo.

 #include  #include  #include  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); } 

Un’altra versione

 #include  #include  #include  #include  #include  using namespace std; void permute(string& list, int level, vector& 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 v; cout << "input character set >"; cin >> anagrama; permute(anagrama, 0, v); sort(v.begin(), v.end()); copy(v.begin(), v.end(), ostream_iterator(cout, "\n")); } 

@alexander l’output di questo programma è nell’ordine esatto richiesto dall’utente:

QUI, è un codice più semplice per generare tutte le combinazioni / permutazioni di un determinato array senza includere alcune librerie speciali (solo iostream.h e string sono inclusi) e senza utilizzare alcuni namespace speciali del solito (viene usato solo lo spazio dei nomi 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 == jn) alpha[i][j] = ark[n]; else if( (in)== j) alpha[i][j] = ark[ ark.length() - n]; if(ark.length()>=2) { for(int i=0; i=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"< 

e principale :

 int main() { string a; int ch; do { system("CLS"); cout<<"PERMUNATING BY ARK's ALGORITH"<>ch; } while (ch!=0); return 0; } 

SPERANZA! ti aiuta! se hai problemi con la comprensione della logica, commenta qui sotto e io modificherò.

 /*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 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 CharMap; typedef CharMap::iterator CharItr; typedef std::pair 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<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++; } } } } 

Ne ho scritto uno senza una funzione già implementata anche su modelli e contenitori. in realtà è stato scritto prima in C, ma è stato trasformato in C ++.

facile da capire ma scarsa efficienza, e il suo output è quello che vuoi, ordinato.

 #include  #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<i;j--) ch[j] = ch[j-1]; ch[i] = temp; //and shift back agian } return 1; } int main(void) { func(N); return 0; }