Programm zum Ausdruck von Permutationen bestimmter Elemente

Ich habe kürzlich an einem ACM-zertifizierten Programmierwettbewerb teilgenommen. Das ist die Frage, die ich damals nicht beantworten konnte:

“Bei einem Array von ganzen Zahlen mit n Elementen schreiben Sie ein Programm, um alle Permutationen zu drucken.”

Bitte sag mir, wie ich diese Frage mache. Gibt es einen Algorithmus für diese Art von Fragen?

Angenommen, es gibt keine Wiederholungen: Ändern Sie einfach jedes Element mit allen möglichen folgenden Elementen und rufen Sie die function rekursiv auf.

void permute(int *array,int i,int length) { if (length == i){ printArray(array,length); return; } int j = i; for (j = i; j < length; j++) { swap(array+i,array+j); permute(array,i+1,length); swap(array+i,array+j); } return; } 

Sie können den Code mit den printArray() swap() und printArray() die mit einem Basis-Testfall unter ideone ausgeführt werden

Bonus : Dies ist vergleichbar mit der Idee von fisher-yates shuffle , aber hier - um das Element bei i mit einem zufällig gewählten folgenden Element zu tauschen - tauscht man es mit jedem von ihnen - jeweils einzeln.

Ein rekursiver Ansatz sollte gut gehen:

 If the list is empty Return the only possible permutation, an empty list. Else For each element of the list Put the element at the first place (ie swap it with the first element) (If the element is same as the first one, don't swap) Recursively find all the permutations of the rest of the list 

Dieser Algorithmus wird keine wiederholten Permutationen erzeugen.

Hier ist eine Python-Implementierung:

 def permute(s): if len(s) == 0: return [[]] ret = [s[0:1] + x for x in permute(s[1:])] for i in range(1, len(s)): if s[i] == s[0]: continue s[0], s[i] = s[i], s[0] ret += [s[0:1] + x for x in permute(s[1:])] return ret s = [0, 1, 2, 3] for x in permute(s): print x 

Die ähnliche Sache in C sollte so sein:

 void swap(char* str, int i, int j) { char temp = str[i]; str[i] = str[j]; str[j] = temp; } void permute(char *string, int start, int end) { if(start == end) { printf("%s\n", string); return; } permute(string, start + 1, end); int i; for(i = start + 1; i < end; i++) { if(string[start] == string[i]) continue; swap(string, start, i); permute(string, start + 1, end); swap(string, start, i); } } 

Hier ist eine iterative Lösung:

Sortiere zuerst das Array.

  • Finde maximalen Index ia [i + 1]. (Wenn kein solcher Index existiert, gibt es keine weiteren Permutationen)

Finde maximalen Index j

Tausche a [i] und a [j].

Umkehren Sie a [i + 1] .. a [n-1] und gehen Sie zu Schritt *.

Um die Permutation zu bekommen, die Sie verwenden müssen, um eine Rückwirkung und Rückverfolgung zu erreichen, können Sie es auch mit Brute-Force lösen, aber es wird komplex

  void swap(int *x1,int *x2) { int x=*x1; *x1=*x2; *x2=x; } void per(int *arr,int st,int ls) { int i=0; if(st==ls) { int k; for(k=0;k