Algorithmus zum Generieren aller möglichen Permutationen einer Liste?

119

Angenommen, ich habe eine Liste von n Elementen, ich weiß, dass es n gibt! Möglichkeiten, diese Elemente zu bestellen. Was ist ein Algorithmus, um alle möglichen Ordnungen dieser Liste zu generieren? Beispiel, ich habe Liste [a, b, c]. Der Algorithmus würde [[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b] zurückgeben , ein]].

Ich lese dies hier http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Aber Wikipedia hat es nie gut erklärt. Ich verstehe nicht viel davon.

fent
quelle
5
Ich habe eine ausführliche Antwort auf eine andere Frage zum einmaligen Generieren von Permutationen geschrieben. Ich denke, es wird für Sie von Interesse sein: stackoverflow.com/questions/1506078/…
Joren
2
Dies kann Ihr Problem lösen en.wikipedia.org/wiki/Heap's_algorithm
Felix

Antworten:

96

Grundsätzlich werden für jedes Element von links nach rechts alle Permutationen der verbleibenden Elemente generiert (und jedes wird mit den aktuellen Elementen hinzugefügt). Dies kann rekursiv (oder iterativ, wenn Sie Schmerzen mögen) erfolgen, bis der letzte Punkt erreicht ist und an diesem Punkt nur noch eine mögliche Reihenfolge vorliegt.

Mit der Liste [1,2,3,4] werden also alle Permutationen generiert, die mit 1 beginnen, dann alle Permutationen, die mit 2 beginnen, dann 3 und dann 4.

Dies reduziert effektiv das Problem vom Finden von Permutationen einer Liste von vier Elementen auf eine Liste von drei Elementen. Nach dem Reduzieren auf 2 und dann 1 Artikellisten werden alle gefunden.
Beispiel für Prozesspermutationen mit 3 farbigen Kugeln:
Rote, grüne und blaue Kugeln bestellten Permutationsbild(von https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg - https://commons.wikimedia.org/wiki/File:Permutations_RGB. svg )

Wirbelwind
quelle
2
Ich habe zuerst auch darüber nachgedacht, aber dann würde das aktuelle Element nicht zwischen einige der folgenden Elemente eingefügt. Es würden also nicht alle Permutationen erzeugt.
Fent
@LLer sorry, habe meine Antwort von "folgend" auf "verbleibend" aktualisiert, um dies zu klären. Es funktioniert aber gut. Überprüfen Sie es, indem Sie den Code schreiben und sicherstellen, dass Sie 4 erhalten! unterschiedliche Ergebnisse.
WhirlWind
2
int-Permutationen (int n, Vektor <int> a) {statische int num_permutations = 0; if (n == (a.size () - 1)) {for (int i = 0; i <a.size (); i ++) cout << a [i] << ""; cout << "\ n"; num_permutations ++; } else {für (int i = n + 1; i <= a.size (); i ++) {Permutationen (n + 1, a); wenn (i <a.size ()) int temp = a [n], a [n] = a [i], a [i] = temp; }} return num_permutations; } int main (void) {vector <int> v; v.push_back (1); ... Permutationen zurückgeben (0, v); }
Somesh
Ups - ich bin mir nicht sicher, wie ich den Code in einem Kommentar formatieren soll ... Habe den Code mit 7 getestet und 5040 erhalten. Danke an @WhirlWind für den Vorschlag.
Irgendwann
ändert sich dieses Algo nicht, wenn Sie 2 oder 3 rote Kugeln Nr. 1 anstelle von nur 1 von jeder Farbe haben können?
Alexander Mills
26

Hier ist ein Algorithmus in Python, der auf einem Array funktioniert:

def permute(xs, low=0):
    if low + 1 >= len(xs):
        yield xs
    else:
        for p in permute(xs, low + 1):
            yield p        
        for i in range(low + 1, len(xs)):        
            xs[low], xs[i] = xs[i], xs[low]
            for p in permute(xs, low + 1):
                yield p        
            xs[low], xs[i] = xs[i], xs[low]

for p in permute([1, 2, 3, 4]):
    print p

Sie können den Code hier selbst ausprobieren: http://repl.it/J9v

cdiggins
quelle
Können Sie bitte den Ertragsteil erklären? Ich konnte den Code nicht trocken laufen lassen. Danke im Voraus.
Agniswar Bakshi
Die Stack Overflow-Frage unter stackoverflow.com/questions/104420/… besagt, dass es ab Version 2.6 ein Standardbibliotheksmodul gibt und eine Antwort mit einer 6-zeiligen Lösung in einer Funktion zum Abrufen von Listenpermutationen .
Edward
@Agniswar Auf einen Blick wird die Yield-Anweisung verwendet, um Generatoren zu definieren, wobei die Rückgabe einer Funktion ersetzt wird, um dem Aufrufer ein Ergebnis zu liefern, ohne lokale Variablen zu zerstören. Im Gegensatz zu einer Funktion, bei der bei jedem Aufruf mit einem neuen Satz von Variablen begonnen wird, setzt ein Generator die Ausführung dort fort, wo sie aufgehört hat. pythoncentral.io/python-generators-and-yield-keyword
MSS
Diese Lösung funktioniert nicht, wenn eine Liste identischer Einträge verarbeitet wird.
KaiserKatze
Danke für das Teilen. Dies ist intuitiv und effizient, obwohl die Ausgabe nicht in lexikografischer Reihenfolge erfolgt.
Sam
16

Hier gibt es bereits viele gute Lösungen, aber ich möchte mitteilen, wie ich dieses Problem selbst gelöst habe, und hoffe, dass dies für jemanden hilfreich sein kann, der auch seine eigene Lösung ableiten möchte.

Nach einigem Nachdenken über das Problem habe ich zwei folgende Schlussfolgerungen gezogen:

  1. Für die Liste Lder Größen ngibt es die gleiche Anzahl von Lösungen, beginnend mit L 1 , L 2 ... L n Elementen der Liste. Da es insgesamt n!Permutationen der Größenliste gibt n, erhalten wir n! / n = (n-1)!Permutationen in jeder Gruppe.
  2. Die Liste der 2 Elemente hat nur 2 Permutationen => [a,b]und [b,a].

Mit diesen beiden einfachen Ideen habe ich den folgenden Algorithmus abgeleitet:

permute array
    if array is of size 2
       return first and second element as new array
       return second and first element as new array
    else
        for each element in array
            new subarray = array with excluded element
            return element + permute subarray

So habe ich das in C # implementiert:

public IEnumerable<List<T>> Permutate<T>(List<T> input)
{
    if (input.Count == 2) // this are permutations of array of size 2
    {
        yield return new List<T>(input);
        yield return new List<T> {input[1], input[0]}; 
    }
    else
    {
        foreach(T elem in input) // going through array
        {
            var rlist = new List<T>(input); // creating subarray = array
            rlist.Remove(elem); // removing element
            foreach(List<T> retlist in Permutate(rlist))
            {
                retlist.Insert(0,elem); // inserting the element at pos 0
                yield return retlist;
            }

        }
    }
}
Alexander Galkin
quelle
16

Die Antwort von Wikipedia auf "lexikografische Reihenfolge" erscheint mir im Kochbuchstil vollkommen explizit. Es zitiert einen Ursprung des Algorithmus aus dem 14. Jahrhundert!

Ich habe gerade eine schnelle Implementierung des Wikipedia-Algorithmus in Java geschrieben, um dies zu überprüfen, und es war kein Problem. Aber was Sie in Ihrem Q als Beispiel haben, ist NICHT "alle Permutationen auflisten", sondern "eine LISTE aller Permutationen", so dass Wikipedia für Sie keine große Hilfe sein wird. Sie benötigen eine Sprache, in der Listen von Permutationen erstellt werden können. Und glauben Sie mir, einige Milliarden lange Listen werden normalerweise nicht in imperativen Sprachen behandelt. Sie möchten wirklich eine nicht strenge funktionale Programmiersprache, in der Listen ein erstklassiges Objekt sind, um Dinge herauszuholen, ohne die Maschine dem Hitzetod des Universums nahe zu bringen.

Das ist einfach. In Standard-Haskell oder einer modernen FP-Sprache:

-- perms of a list
perms :: [a] -> [ [a] ]
perms (a:as) = [bs ++ a:cs | perm <- perms as, (bs,cs) <- splits perm]
perms []     = [ [] ]

und

-- ways of splitting a list into two parts
splits :: [a] -> [ ([a],[a]) ]
splits []     = [ ([],[]) ]
splits (a:as) = ([],a:as) : [(a:bs,cs) | (bs,cs) <- splits as]
Peter Breuer
quelle
9

Wie WhirlWind sagte, fängst du am Anfang an.

Sie tauschen den Cursor mit jedem verbleibenden Wert aus, einschließlich des Cursors selbst. Dies sind alles neue Instanzen (ich habe ein int[]und array.clone()im Beispiel verwendet).

Führen Sie dann Permutationen für alle diese verschiedenen Listen durch und stellen Sie sicher, dass sich der Cursor rechts befindet.

Wenn keine verbleibenden Werte mehr vorhanden sind (der Cursor befindet sich am Ende), drucken Sie die Liste. Dies ist die Stoppbedingung.

public void permutate(int[] list, int pointer) {
    if (pointer == list.length) {
        //stop-condition: print or process number
        return;
    }
    for (int i = pointer; i < list.length; i++) {
        int[] permutation = (int[])list.clone();.
        permutation[pointer] = list[i];
        permutation[i] = list[pointer];
        permutate(permutation, pointer + 1);
    }
}
Dinadineke
quelle
8

Rekursiv erfordert immer einige mentale Anstrengungen, um aufrechtzuerhalten. Und für große Zahlen ist die Fakultät leicht riesig und der Stapelüberlauf wird leicht ein Problem sein.

Für kleine Zahlen (3 oder 4, was meistens vorkommt) sind mehrere Schleifen recht einfach und unkompliziert. Es ist bedauerlich, dass Antworten mit Schleifen nicht bewertet wurden.

Beginnen wir mit der Aufzählung (und nicht mit der Permutation). Lesen Sie den Code einfach als Pseudo-Perl-Code.

$foreach $i1 in @list
    $foreach $i2 in @list 
        $foreach $i3 in @list
            print "$i1, $i2, $i3\n"

Aufzählung tritt häufiger auf als Permutation. Wenn jedoch eine Permutation erforderlich ist, fügen Sie einfach die folgenden Bedingungen hinzu:

$foreach $i1 in @list
    $foreach $i2 in @list 
        $if $i2==$i1
            next
        $foreach $i3 in @list
            $if $i3==$i1 or $i3==$i2
                next
            print "$i1, $i2, $i3\n"

Wenn Sie nun wirklich eine allgemeine Methode für große Listen benötigen, können wir die Radix-Methode verwenden. Betrachten Sie zunächst das Aufzählungsproblem:

$n=@list
my @radix
$for $i=0:$n
    $radix[$i]=0
$while 1
    my @temp
    $for $i=0:$n
        push @temp, $list[$radix[$i]]
    print join(", ", @temp), "\n"
    $call radix_increment

subcode: radix_increment
    $i=0
    $while 1
        $radix[$i]++
        $if $radix[$i]==$n
            $radix[$i]=0
            $i++
        $else
            last
    $if $i>=$n
        last

Das Radix-Inkrement ist im Wesentlichen die Zählung von Zahlen (in der Basis der Anzahl der Listenelemente).

Wenn Sie nun Permutaion benötigen, fügen Sie einfach die Checks in die Schleife ein:

subcode: check_permutation
    my @check
    my $flag_dup=0
    $for $i=0:$n
        $check[$radix[$i]]++
        $if $check[$radix[$i]]>1
            $flag_dup=1
            last
    $if $flag_dup
        next

Bearbeiten: Der obige Code sollte funktionieren, aber für die Permutation könnte radix_increment verschwenderisch sein. Wenn also Zeit ein praktisches Anliegen ist, müssen wir radix_increment in permute_inc ändern:

subcode: permute_init
    $for $i=0:$n
        $radix[$i]=$i

subcode: permute_inc                                       
    $max=-1                                                
    $for $i=$n:0                                           
        $if $max<$radix[$i]                                
            $max=$radix[$i]                                
        $else                                              
            $for $j=$n:0                                   
                $if $radix[$j]>$radix[$i]                  
                    $call swap, $radix[$i], $radix[$j]     
                    break                                  
            $j=$i+1                                        
            $k=$n-1                                        
            $while $j<$k                                   
                $call swap, $radix[$j], $radix[$k]         
                $j++                                       
                $k--                                       
            break                                          
    $if $i<0                                               
        break                                              

Natürlich ist dieser Code jetzt logisch komplexer, ich werde ihn dem Leser überlassen.

Hui Zhou
quelle
7

Geben Sie hier die Bildbeschreibung ein

// C program to print all permutations with duplicates allowed
#include <stdio.h>
#include <string.h>

/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */

void permute(char *a, int l, int r)
{
   int i;
   if (l == r)
     printf("%s\n", a);
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));
          permute(a, l+1, r);
          swap((a+l), (a+i)); //backtrack
       }
   }
}

/* Driver program to test above functions */
int main()
{
    char str[] = "ABC";
    int n = strlen(str);
    permute(str, 0, n-1);
    return 0;
}

Referenz: Geeksforgeeks.org

Sazzad Hissain Khan
quelle
5

Wenn sich jemand fragt, wie man in Permutation in Javascript vorgeht.

Idee / Pseudocode

  1. Wählen Sie jeweils ein Element aus
  2. Permutieren Sie den Rest des Elements und fügen Sie dann das ausgewählte Element zur gesamten Permutation hinzu

beispielsweise. 'a' + permutieren (bc). Permute von bc wäre bc & cb. Fügen Sie nun diese beiden hinzu, um abc, acb zu erhalten. In ähnlicher Weise wird durch Auswahl von b + permute (ac) bac, bca ... provoziert und weitergemacht.

Schauen Sie sich jetzt den Code an

function permutations(arr){

   var len = arr.length, 
       perms = [],
       rest,
       picked,
       restPerms,
       next;

    //for one or less item there is only one permutation 
    if (len <= 1)
        return [arr];

    for (var i=0; i<len; i++)
    {
        //copy original array to avoid changing it while picking elements
        rest = Object.create(arr);

        //splice removed element change array original array(copied array)
        //[1,2,3,4].splice(2,1) will return [3] and remaining array = [1,2,4]
        picked = rest.splice(i, 1);

        //get the permutation of the rest of the elements
        restPerms = permutations(rest);

       // Now concat like a+permute(bc) for each
       for (var j=0; j<restPerms.length; j++)
       {
           next = picked.concat(restPerms[j]);
           perms.push(next);
       }
    }

   return perms;
}

Nehmen Sie sich Zeit, um dies zu verstehen. Ich habe diesen Code erhalten von ( Pertumation in JavaScript )

Jhankar Mahbub
quelle
Ich habe an etwas Ähnliches gedacht, aber sollten Sie das ausgewählte Element nicht sowohl vorne als auch am Ende der restParams hinzufügen? In diesem Fall sind für 'abc', wenn Sie a auswählen, die 'bc'-Permutationen' bc 'und' cb '. Wenn Sie 'a' zurück zur Liste hinzufügen, sollten Sie es nicht vorne als 'a + bc' + 'a + cb', sondern am Ende als 'bc + a' + 'cb + a' von hinzufügen Die Liste?
Artimus
Sie erhalten diese Permutationen, wenn Sie mit 'b' bzw. 'c' beginnen. (dh der zweite und dritte Lauf der äußeren "for" -Schleife)
Ryan O'Neill
3

Ein anderes in Python, es ist nicht als @ cdiggins vorhanden, aber ich denke, es ist einfacher zu verstehen

def permute(num):
    if len(num) == 2:
        # get the permutations of the last 2 numbers by swapping them
        yield num
        num[0], num[1] = num[1], num[0]
        yield num
    else:
        for i in range(0, len(num)):
            # fix the first number and get the permutations of the rest of numbers
            for perm in permute(num[0:i] + num[i+1:len(num)]):
                yield [num[i]] + perm

for p in permute([1, 2, 3, 4]):
    print p
Zhywu
quelle
3

Ich dachte daran, einen Code zu schreiben, um die Permutationen einer bestimmten Ganzzahl beliebiger Größe zu erhalten, dh mit einer Zahl von 4567 erhalten wir alle möglichen Permutationen bis 7654 ... Also arbeitete ich daran und fand einen Algorithmus und implementierte ihn schließlich hier ist der in "c" geschriebene Code. Sie können es einfach kopieren und auf beliebigen Open Source-Compilern ausführen. Einige Fehler warten jedoch darauf, behoben zu werden. Bitte schätzen.

Code:

#include <stdio.h>
#include <conio.h>
#include <malloc.h>

                //PROTOTYPES

int fact(int);                  //For finding the factorial
void swap(int*,int*);           //Swapping 2 given numbers
void sort(int*,int);            //Sorting the list from the specified path
int imax(int*,int,int);         //Finding the value of imax
int jsmall(int*,int);           //Gives position of element greater than ith but smaller than rest (ahead of imax)
void perm();                    //All the important tasks are done in this function


int n;                         //Global variable for input OR number of digits

void main()
{
int c=0;

printf("Enter the number : ");
scanf("%d",&c);
perm(c);
getch();
}

void perm(int c){
int *p;                     //Pointer for allocating separate memory to every single entered digit like arrays
int i, d;               
int sum=0;
int j, k;
long f;

n = 0;

while(c != 0)               //this one is for calculating the number of digits in the entered number
{
    sum = (sum * 10) + (c % 10);
    n++;                            //as i told at the start of loop
    c = c / 10;
}

f = fact(n);                        //It gives the factorial value of any number

p = (int*) malloc(n*sizeof(int));                //Dynamically allocation of array of n elements

for(i=0; sum != 0 ; i++)
{
    *(p+i) = sum % 10;                               //Giving values in dynamic array like 1234....n separately
    sum = sum / 10;
}

sort(p,-1);                                         //For sorting the dynamic array "p"

for(c=0 ; c<f/2 ; c++) {                        //Most important loop which prints 2 numbers per loop, so it goes upto 1/2 of fact(n)

    for(k=0 ; k<n ; k++)
        printf("%d",p[k]);                       //Loop for printing one of permutations
    printf("\n");

    i = d = 0;
    i = imax(p,i,d);                            //provides the max i as per algo (i am restricted to this only)
    j = i;
    j = jsmall(p,j);                            //provides smallest i val as per algo
    swap(&p[i],&p[j]);

    for(k=0 ; k<n ; k++)
        printf("%d",p[k]);
    printf("\n");

    i = d = 0;
    i = imax(p,i,d);
    j = i;
    j = jsmall(p,j);
    swap(&p[i],&p[j]);

    sort(p,i);
}
free(p);                                        //Deallocating memory
}

int fact (int a)
{
long f=1;
while(a!=0)
{
    f = f*a;
    a--;
}
return f;
}


void swap(int *p1,int *p2)
{
int temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
return;
}


void sort(int*p,int t)
{
int i,temp,j;
for(i=t+1 ; i<n-1 ; i++)
{
    for(j=i+1 ; j<n ; j++)
    {
        if(*(p+i) > *(p+j))
        {
            temp = *(p+i);
            *(p+i) = *(p+j);
            *(p+j) = temp;
        }
    }
}
}


int imax(int *p, int i , int d)
{
    while(i<n-1 && d<n-1)
{
    if(*(p+d) < *(p+d+1))
    {   
        i = d;
        d++;
    }
    else
        d++;
}
return i;
}


int jsmall(int *p, int j)
{
int i,small = 32767,k = j;
for (i=j+1 ; i<n ; i++)
{
    if (p[i]<small && p[i]>p[k])
    {     
       small = p[i];
       j = i;
    }
}
return j;
}
FreakPirate
quelle
3
void permutate(char[] x, int i, int n){
    x=x.clone();
    if (i==n){
        System.out.print(x);
        System.out.print(" ");
        counter++;}
    else
    {
        for (int j=i; j<=n;j++){
     //   System.out.print(temp); System.out.print(" ");    //Debugger
        swap (x,i,j);
      //  System.out.print(temp); System.out.print(" "+"i="+i+" j="+j+"\n");// Debugger
        permutate(x,i+1,n);
    //    swap (temp,i,j);
    }
    }
}

void swap (char[] x, int a, int b){
char temp = x[a];
x[a]=x[b];
x[b]=temp;
}

Ich habe diesen erstellt. basierend auf zu permutierten Forschungsergebnissen (qwe, 0, qwe.length-1); Nur damit Sie wissen, können Sie es mit oder ohne Backtrack tun

Luigi Mackenzie C. Brito
quelle
3

Hier ist eine Spielzeug-Ruby-Methode, die so funktioniert und #permutation.to_afür verrückte Leute möglicherweise besser lesbar ist. Es ist hella langsam, aber auch 5 Zeilen.

def permute(ary)
  return [ary] if ary.size <= 1
  ary.collect_concat.with_index do |e, i|
    rest = ary.dup.tap {|a| a.delete_at(i) }
    permute(rest).collect {|a| a.unshift(e) }
  end
end
Jenner La Fave
quelle
3

Ich habe diese rekursive Lösung in ANSI C geschrieben. Jede Ausführung der Permutate-Funktion bietet eine andere Permutation, bis alle abgeschlossen sind. Globale Variablen können auch für die Variablen Fakt und Anzahl verwendet werden.

#include <stdio.h>
#define SIZE 4

void Rotate(int vec[], int size)
{
    int i, j, first;

    first = vec[0];
    for(j = 0, i = 1; i < size; i++, j++)
    {
        vec[j] = vec[i];
    }
    vec[j] = first;
}

int Permutate(int *start, int size, int *count)
{
    static int fact;

    if(size > 1)
    {
        if(Permutate(start + 1, size - 1, count))
        {
            Rotate(start, size);
        }
        fact *= size;
    }
    else
    {
        (*count)++;
        fact = 1;
    }

    return !(*count % fact);
}

void Show(int vec[], int size)
{
    int i;

    printf("%d", vec[0]);
    for(i = 1; i < size; i++)
    {
        printf(" %d", vec[i]);
    }
    putchar('\n');
}

int main()
{
    int vec[] = { 1, 2, 3, 4, 5, 6 }; /* Only the first SIZE items will be permutated */
    int count = 0;

    do
    {
        Show(vec, SIZE);
    } while(!Permutate(vec, SIZE, &count));

    putchar('\n');
    Show(vec, SIZE);
    printf("\nCount: %d\n\n", count);

    return 0;
}
Horacio
quelle
3

Java-Version

/**
 * @param uniqueList
 * @param permutationSize
 * @param permutation
 * @param only            Only show the permutation of permutationSize,
 *                        else show all permutation of less than or equal to permutationSize.
 */
public static void my_permutationOf(List<Integer> uniqueList, int permutationSize, List<Integer> permutation, boolean only) {
    if (permutation == null) {
        assert 0 < permutationSize && permutationSize <= uniqueList.size();
        permutation = new ArrayList<>(permutationSize);
        if (!only) {
            System.out.println(Arrays.toString(permutation.toArray()));
        }
    }
    for (int i : uniqueList) {
        if (permutation.contains(i)) {
            continue;
        }
        permutation.add(i);
        if (!only) {
            System.out.println(Arrays.toString(permutation.toArray()));
        } else if (permutation.size() == permutationSize) {
            System.out.println(Arrays.toString(permutation.toArray()));
        }
        if (permutation.size() < permutationSize) {
            my_permutationOf(uniqueList, permutationSize, permutation, only);
        }
        permutation.remove(permutation.size() - 1);
    }
}

Z.B

public static void main(String[] args) throws Exception { 
    my_permutationOf(new ArrayList<Integer>() {
        {
            add(1);
            add(2);
            add(3);

        }
    }, 3, null, true);
}

Ausgabe:

  [1, 2, 3]
  [1, 3, 2]
  [2, 1, 3]
  [2, 3, 1]
  [3, 1, 2]
  [3, 2, 1]
Bruce Zu
quelle
3

in PHP

$set=array('A','B','C','D');

function permutate($set) {
    $b=array();
    foreach($set as $key=>$value) {
        if(count($set)==1) {
            $b[]=$set[$key];
        }
        else {
            $subset=$set;
            unset($subset[$key]);
            $x=permutate($subset);
            foreach($x as $key1=>$value1) {
                $b[]=$value.' '.$value1;
            }
        }
    }
    return $b;
}

$x=permutate($set);
var_export($x);
Nerdface
quelle
3

Hier ist der Code in Python zum Drucken aller möglichen Permutationen einer Liste:

def next_perm(arr):
    # Find non-increasing suffix
    i = len(arr) - 1
    while i > 0 and arr[i - 1] >= arr[i]:
        i -= 1
    if i <= 0:
        return False

    # Find successor to pivot
    j = len(arr) - 1
    while arr[j] <= arr[i - 1]:
        j -= 1
    arr[i - 1], arr[j] = arr[j], arr[i - 1]

    # Reverse suffix
    arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
    print arr
    return True

def all_perm(arr):
    a = next_perm(arr)
    while a:
        a = next_perm(arr)
    arr = raw_input()
    arr.split(' ')
    arr = map(int, arr)
    arr.sort()
    print arr
    all_perm(arr)

Ich habe einen lexikografischen Ordnungsalgorithmus verwendet, um alle möglichen Permutationen zu erhalten, aber ein rekursiver Algorithmus ist effizienter. Den Code für den rekursiven Algorithmus finden Sie hier: Python-Rekursionspermutationen

Anuj Mittal
quelle
3
public class PermutationGenerator
{
    private LinkedList<List<int>> _permutationsList;
    public void FindPermutations(List<int> list, int permutationLength)
    {
        _permutationsList = new LinkedList<List<int>>();
        foreach(var value in list)
        {
            CreatePermutations(value, permutationLength);
        }
    }

    private void CreatePermutations(int value, int permutationLength)
    {
        var node = _permutationsList.First;
        var last = _permutationsList.Last;
        while (node != null)
        {
            if (node.Value.Count < permutationLength)
            {
                GeneratePermutations(node.Value, value, permutationLength);
            }
            if (node == last)
            {
                break;
            }
            node = node.Next;
        }

        List<int> permutation = new List<int>();
        permutation.Add(value);
        _permutationsList.AddLast(permutation);
    }

    private void GeneratePermutations(List<int> permutation, int value, int permutationLength)
    {
       if (permutation.Count < permutationLength)
        {
            List<int> copyOfInitialPermutation = new List<int>(permutation);
            copyOfInitialPermutation.Add(value);
            _permutationsList.AddLast(copyOfInitialPermutation);
            List<int> copyOfPermutation = new List<int>();
            copyOfPermutation.AddRange(copyOfInitialPermutation);
            int lastIndex = copyOfInitialPermutation.Count - 1;
            for (int i = lastIndex;i > 0;i--)
            {
                int temp = copyOfPermutation[i - 1];
                copyOfPermutation[i - 1] = copyOfPermutation[i];
                copyOfPermutation[i] = temp;

                List<int> perm = new List<int>();
                perm.AddRange(copyOfPermutation);
                _permutationsList.AddLast(perm);
            }
        }
    }

    public void PrintPermutations(int permutationLength)
    {
        int count = _permutationsList.Where(perm => perm.Count() == permutationLength).Count();
        Console.WriteLine("The number of permutations is " + count);
    }
}
Bahruz Balabayov
quelle
es ist eine nützliche Antwort
Ayaz Alifov
2

In der Scala

    def permutazione(n: List[Int]): List[List[Int]] = permutationeAcc(n, Nil)



def permutationeAcc(n: List[Int], acc: List[Int]): List[List[Int]] = {

    var result: List[List[Int]] = Nil
    for (i ← n if (!(acc contains (i))))
        if (acc.size == n.size-1)
            result = (i :: acc) :: result
        else
            result = result ::: permutationeAcc(n, i :: acc)
    result
}
Marco
quelle
2

Dies ist eine Java-Version für die Permutation

public class Permutation {

    static void permute(String str) {
        permute(str.toCharArray(), 0, str.length());
    }

    static void permute(char [] str, int low, int high) {
        if (low == high) {
            System.out.println(str);
            return;
        }

        for (int i=low; i<high; i++) {
            swap(str, i, low);
            permute(str, low+1, high);
            swap(str, low, i);
        }

    }

    static void swap(char [] array, int i, int j) {
        char t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}
杨小勇
quelle
2

Hier ist eine Implementierung für ColdFusion (erfordert CF10 aufgrund des Merge-Arguments zu ArrayAppend ()):

public array function permutateArray(arr){

    if (not isArray(arguments.arr) ) {
        return ['The ARR argument passed to the permutateArray function is not of type array.'];    
    }

    var len = arrayLen(arguments.arr);
    var perms = [];
    var rest = [];
    var restPerms = [];
    var rpLen = 0;
    var next = [];

    //for one or less item there is only one permutation 
    if (len <= 1) {
        return arguments.arr;
    }

    for (var i=1; i <= len; i++) {
        // copy the original array so as not to change it and then remove the picked (current) element
        rest = arraySlice(arguments.arr, 1);
        arrayDeleteAt(rest, i);

         // recursively get the permutation of the rest of the elements
         restPerms = permutateArray(rest);
         rpLen = arrayLen(restPerms);

        // Now concat each permutation to the current (picked) array, and append the concatenated array to the end result
        for (var j=1; j <= rpLen; j++) {
            // for each array returned, we need to make a fresh copy of the picked(current) element array so as to not change the original array
            next = arraySlice(arguments.arr, i, 1);
            arrayAppend(next, restPerms[j], true);
            arrayAppend(perms, next);
        }
     }

    return perms;
}

Basierend auf der obigen js-Lösung von KhanSharp.

earachefl
quelle
Eine Erklärung der Gesamtstrategie Ihres Algorithmus wäre ein guter Weg, um diese Antwort zu verbessern.
Richard
Warum also die Abwertung? Dies ist eine funktionierende Implementierung.
earachefl
@Richard, die Gesamtstrategie wurde oben von Whirlwind und anderen erklärt. Ich sehe Ihren Kommentar zu allen anderen Antworten nicht als Implementierungen ohne Erklärungen.
earachefl
1

Ich weiß, dass dies im heutigen Stackoverflow ein sehr sehr altes und sogar nicht zum Thema gehörendes Thema ist, aber ich wollte trotzdem eine freundliche Javascript-Antwort beisteuern, aus dem einfachen Grund, dass es in Ihrem Browser ausgeführt wird.

Ich habe auch den debuggerDirektiven-Haltepunkt hinzugefügt, damit Sie den Code (Chrome erforderlich) schrittweise durchgehen können, um zu sehen, wie dieser Algorithmus funktioniert. Öffnen Sie Ihre Entwicklungskonsole in Chrome ( F12in Windows oderCMD + OPTION + I Mac) und klicken Sie dann auf "Code-Snippet ausführen". Dies implementiert denselben exakten Algorithmus, den @WhirlWind in seiner Antwort vorgestellt hat.

Ihr Browser sollte die Ausführung an der debuggerDirektive anhalten. VerwendenF8 diese , um die Codeausführung fortzusetzen.

Gehen Sie den Code durch und sehen Sie, wie es funktioniert!

function permute(rest, prefix = []) {
  if (rest.length === 0) {
    return [prefix];
  }
  return (rest
    .map((x, index) => {
      const oldRest = rest;
      const oldPrefix = prefix;
      // the `...` destructures the array into single values flattening it
      const newRest = [...rest.slice(0, index), ...rest.slice(index + 1)];
      const newPrefix = [...prefix, x];
      debugger;

      const result = permute(newRest, newPrefix);
      return result;
    })
    // this step flattens the array of arrays returned by calling permute
    .reduce((flattened, arr) => [...flattened, ...arr], [])
  );
}
console.log(permute([1, 2, 3]));

Rico Kahler
quelle
1

In der folgenden Java-Lösung nutzen wir die Tatsache, dass Strings unveränderlich sind, um zu vermeiden, dass die Ergebnismenge bei jeder Iteration geklont wird.

Die Eingabe ist ein String, sagen wir "abc", und die Ausgabe enthält alle möglichen Permutationen:

abc
acb
bac
bca
cba
cab

Code:

public static void permute(String s) {
    permute(s, 0);
}

private static void permute(String str, int left){
    if(left == str.length()-1) {
        System.out.println(str);
    } else {
        for(int i = left; i < str.length(); i++) {
            String s = swap(str, left, i);
            permute(s, left+1);
        }
    }
}

private static String swap(String s, int left, int right) {
    if (left == right)
        return s;

    String result = s.substring(0, left);
    result += s.substring(right, right+1);
    result += s.substring(left+1, right);
    result += s.substring(left, left+1);
    result += s.substring(right+1);
    return result;
}

Der gleiche Ansatz kann auf Arrays angewendet werden (anstelle einer Zeichenfolge):

public static void main(String[] args) {
    int[] abc = {1,2,3};
    permute(abc, 0);
}
public static void permute(int[] arr, int index) {
    if (index == arr.length) {
        System.out.println(Arrays.toString(arr));
    } else {
        for (int i = index; i < arr.length; i++) {
            int[] permutation = arr.clone();
            permutation[index] = arr[i];
            permutation[i] = arr[index];
            permute(permutation, index + 1);
        }
    }
}
Alfasin
quelle
1

Es ist meine Lösung für Java:

public class CombinatorialUtils {

    public static void main(String[] args) {
        List<String> alphabet = new ArrayList<>();
        alphabet.add("1");
        alphabet.add("2");
        alphabet.add("3");
        alphabet.add("4");

        for (List<String> strings : permutations(alphabet)) {
            System.out.println(strings);
        }
        System.out.println("-----------");
        for (List<String> strings : combinations(alphabet)) {
            System.out.println(strings);
        }
    }

    public static List<List<String>> combinations(List<String> alphabet) {
        List<List<String>> permutations = permutations(alphabet);
        List<List<String>> combinations = new ArrayList<>(permutations);

        for (int i = alphabet.size(); i > 0; i--) {
            final int n = i;
            combinations.addAll(permutations.stream().map(strings -> strings.subList(0, n)).distinct().collect(Collectors.toList()));
        }
        return combinations;
    }

    public static <T> List<List<T>> permutations(List<T> alphabet) {
        ArrayList<List<T>> permutations = new ArrayList<>();
        if (alphabet.size() == 1) {
            permutations.add(alphabet);
            return permutations;
        } else {
            List<List<T>> subPerm = permutations(alphabet.subList(1, alphabet.size()));
            T addedElem = alphabet.get(0);
            for (int i = 0; i < alphabet.size(); i++) {
                for (List<T> permutation : subPerm) {
                    int index = i;
                    permutations.add(new ArrayList<T>(permutation) {{
                        add(index, addedElem);
                    }});
                }
            }
        }
        return permutations;
    }
}
user2153604
quelle
1

Sie können nicht wirklich über die Lösung eines Permultationsproblems in Rekursion sprechen, ohne eine Implementierung in einer (Dialekt-) Sprache zu veröffentlichen, die Pionierarbeit für die Idee geleistet hat . Der Vollständigkeit halber ist hier eine der Möglichkeiten, die in Schema ausgeführt werden können.

(define (permof wd)
  (cond ((null? wd) '())
        ((null? (cdr wd)) (list wd))
        (else
         (let splice ([l '()] [m (car wd)] [r (cdr wd)])
           (append
            (map (lambda (x) (cons m x)) (permof (append l r)))
            (if (null? r)
                '()
                (splice (cons m l) (car r) (cdr r))))))))

Anruf bekommen (permof (list "foo" "bar" "baz"))wir:

'(("foo" "bar" "baz")
  ("foo" "baz" "bar")
  ("bar" "foo" "baz")
  ("bar" "baz" "foo")
  ("baz" "bar" "foo")
  ("baz" "foo" "bar"))

Ich werde nicht auf die Details des Algorithmus eingehen, da dies in anderen Beiträgen ausreichend erklärt wurde. Die Idee ist die gleiche.

Rekursive Probleme sind jedoch in destruktiven Medien wie Python, C und Java viel schwieriger zu modellieren und zu berücksichtigen, während sie in Lisp oder ML präzise ausgedrückt werden können.

Pie 'Oh' Pah
quelle
0

Hier ist eine rekursive Lösung in PHP. WhirlWinds Beitrag beschreibt die Logik genau. Es ist erwähnenswert, dass das Generieren aller Permutationen in faktorieller Zeit erfolgt. Daher ist es möglicherweise eine gute Idee, stattdessen einen iterativen Ansatz zu verwenden.

public function permute($sofar, $input){
  for($i=0; $i < strlen($input); $i++){
    $diff = strDiff($input,$input[$i]);
    $next = $sofar.$input[$i]; //next contains a permutation, save it
    $this->permute($next, $diff);
  }
}

Die strDiff-Funktion verwendet zwei Zeichenfolgen s1und s2und gibt eine neue Zeichenfolge zurück, in der alles s1ohne Elemente enthalten ist s2(Duplikate sind wichtig). Also, strDiff('finish','i')=> 'fnish'(das zweite 'i' wird nicht entfernt).

Anthony Naddeo
quelle
0

Hier ist ein Algorithmus in R für den Fall, dass jemand vermeiden muss, zusätzliche Bibliotheken zu laden, wie ich es musste.

permutations <- function(n){
    if(n==1){
        return(matrix(1))
    } else {
        sp <- permutations(n-1)
        p <- nrow(sp)
        A <- matrix(nrow=n*p,ncol=n)
        for(i in 1:n){
            A[(i-1)*p+1:p,] <- cbind(i,sp+(sp>=i))
        }
        return(A)
    }
}

Anwendungsbeispiel:

> matrix(letters[permutations(3)],ncol=3)
     [,1] [,2] [,3]
[1,] "a"  "b"  "c" 
[2,] "a"  "c"  "b" 
[3,] "b"  "a"  "c" 
[4,] "b"  "c"  "a" 
[5,] "c"  "a"  "b" 
[6,] "c"  "b"  "a" 
Museful
quelle
0
#!/usr/bin/env python
import time

def permutations(sequence):
  # print sequence
  unit = [1, 2, 1, 2, 1]

  if len(sequence) >= 4:
    for i in range(4, (len(sequence) + 1)):
      unit = ((unit + [i - 1]) * i)[:-1]
      # print unit
    for j in unit:
      temp = sequence[j]
      sequence[j] = sequence[0]
      sequence[0] = temp
      yield sequence
  else:
    print 'You can use PEN and PAPER'


# s = [1,2,3,4,5,6,7,8,9,10]
s = [x for x in 'PYTHON']

print s

z = permutations(s)
try:
  while True:
    # time.sleep(0.0001)
    print next(z)
except StopIteration:
    print 'Done'

['P', 'Y', 'T', 'H', 'O', 'N']
['Y', 'P', 'T', 'H', 'O', 'N']
['T', 'P', 'Y', 'H', 'O', 'N']
['P', 'T', 'Y', 'H', 'O', 'N']
['Y', 'T', 'P', 'H', 'O', 'N']
['T', 'Y', 'P', 'H', 'O', 'N']
['H', 'Y', 'P', 'T', 'O', 'N']
['Y', 'H', 'P', 'T', 'O', 'N']
['P', 'H', 'Y', 'T', 'O', 'N']
['H', 'P', 'Y', 'T', 'O', 'N']
['Y', 'P', 'H', 'T', 'O', 'N']
['P', 'Y', 'H', 'T', 'O', 'N']
['T', 'Y', 'H', 'P', 'O', 'N']
['Y', 'T', 'H', 'P', 'O', 'N']
['H', 'T', 'Y', 'P', 'O', 'N']
['T', 'H', 'Y', 'P', 'O', 'N']
['Y', 'H', 'T', 'P', 'O', 'N']
['H', 'Y', 'T', 'P', 'O', 'N']
['P', 'Y', 'T', 'H', 'O', 'N']
.
.
.
['Y', 'T', 'N', 'H', 'O', 'P']
['N', 'T', 'Y', 'H', 'O', 'P']
['T', 'N', 'Y', 'H', 'O', 'P']
['Y', 'N', 'T', 'H', 'O', 'P']
['N', 'Y', 'T', 'H', 'O', 'P']
Mahmoh
quelle
Die Lösung zeigt, dass Sie die Zeichenfolge nicht gemäß der Anforderung permutiert haben. Die zweite Permutation sollte PYTHNO
Rahul Kadukar
0

Dies ist ein rekursiver Code für Java. Die Idee ist, ein Präfix zu haben, das den Rest der Zeichen hinzufügt:

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str);
    }
}

Beispiel:

Eingabe = "ABC"; Ausgabe:

ABC ACB BAC BCA CAB CBA

Rafael Amsili
quelle
1
Gute Idee, aber ich denke, Sie sollten auch charAt (i) entfernen, strwenn Sie rekursiv anrufen, sonst wird es nicht beendet.
Crystal
1
Wenn Sie kopieren und einfügen möchten, müssen Sie (1) eine Zuordnung vornehmen und (2) sicherstellen, dass alle Änderungen korrekt sind. Für die Zuordnung ist dies perm1 von introcs.cs.princeton.edu/java/23recursion/… . Auch Ihre Bearbeitung ist falsch: strsubstring (0, i) + str.substring (i + 1, n) ist nicht dasselbe wie str, da erstere das Zeichen an Position i weglässt.
Kevin
0

Nur um vollständig zu sein, C ++

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

std::string theSeq = "abc";
do
{
  std::cout << theSeq << endl;
} 
while (std::next_permutation(theSeq.begin(), theSeq.end()));

...

abc
acb
bac
bca
cab
cba
AndersK
quelle
0

Hier ist eine nicht rekursive Lösung in C ++, die die nächste Permutation in aufsteigender Reihenfolge bereitstellt, ähnlich der Funktionalität von std :: next_permutation:

void permute_next(vector<int>& v)
{
  if (v.size() < 2)
    return;

  if (v.size() == 2)
  { 
    int tmp = v[0];
    v[0] = v[1];
    v[1] = tmp;
    return;
  }

  // Step 1: find first ascending-ordered pair from right to left
  int i = v.size()-2;
  while(i>=0)
  { 
    if (v[i] < v[i+1])
      break;
    i--;
  }
  if (i<0) // vector fully sorted in descending order (last permutation)
  {
    //resort in ascending order and return
    sort(v.begin(), v.end());
    return;
  }

  // Step 2: swap v[i] with next higher element of remaining elements
  int pos = i+1;
  int val = v[pos];
  for(int k=i+2; k<v.size(); k++)
    if(v[k] < val && v[k] > v[i])
    {
      pos = k;
      val = v[k];
    }
  v[pos] = v[i];
  v[i] = val;

  // Step 3: sort remaining elements from i+1 ... end
  sort(v.begin()+i+1, v.end());
}
Marios Choudary
quelle