Algorithme for generering av alle permutasjoner

[etse]

Jeg jobber for tiden med et program hvor jeg har bruk for alle permutasjoner av en gitt liste / array. Jeg har meget begrenset med minne og kan derfor ikke ta i bruk stack eller rekursive implementasjoner for å generere disse.

 

Jeg har prøvd å tenke meg frem til en god algoritme for å generere alle mulige permutasjoner uten å bruke hverken stack eller rekursivitet - men klarer ikke komme på noen gode løsninger.

 

Lurer derfor på om noen her kan hjelpe meg.

- Det er rimelig å anta at alle elementene i arrayet er unike, så man trenger ikke ta hensyn til at 2 elementer er like.

[BlueEAGLE]

Dette er en binær tallrekke hvor elementet enten er der eller ikke. Det du gjør da er simpelten å telle fra 0 til 2^n hvor n er antall element.

 

Hvis Eple = 1, Pære = 2, Appelsin = 4 og Melon = 8 så vil 11 være eple, pære og melon, men ikke appelsin.

 

Hvis listen er lang så kan du få problemer med en integer overflow, men det er en annen historie.

[etse]

Kan være du missforstod, er ute etter permutasjoner. Altså gitt listen

[1, 2, 3] så ønsker jeg å lage:

 

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 2, 1]

[3, 1, 2]

 

Dette er enkelt og intuitivt å gjøre om man kan bruke rekursivitet eller en form for stack. Men jeg har ikke tilgang til dynamisk minne uten at koden blir veldig treg. Rekursivitet er ikke støttet av enheten.

[Pydien]

1 2 3

2 1 3 --> flytt første element mot høyre til du kommer mot slutten (1)

2 3 1 --> Nådd slutten her

3 2 1 --> gjør det samme for det nye første elementet (2)

3 1 2 --> Nådd slutten her.

1 3 2 --> gjør det for nye her (3)

 

fortsett slik til du er tilbake til opprinnelige permutasjon.

 

Noe slikt? Burde ikke være så hamslig å implementere.

[Pydien]

Evt kan du muligens hvis du ser for deg en sirkel av verdier:

 

1 2 3 start å skrive fra start til slutt

2 3 1 start å skrive fra andre posisjon og rundt

3 1 2 start å skrive fra 3 posisjon og rundt

 

Så gjør du det samme motsatt vei.

 

3 2 1 start fra slutt

2 1 3 start fra posisjon n-1

1 3 2 start fra posisjon n-2

[snippsat]

Hvilket språk er er det snakk om?

Kan ha en del og si på fremgangsmåte.

 

Du kan se på QuickPerm Algorithm

 

I språk som Python,C#,Ruby vil "yield(Generator)" være naturlig og bruke.

Generator er minneeffektiv ettersom man leser element for element til minne.

 

I C++ er next_permutation() noe og se på.

 

Du kan jo se litt på hvordan det er gjort i Python sin itertool module,skrevet av Raymond Hettinger.

itertools.permutations()

Rask demo.

>>> import itertools
>>> lst = [1, 2, 3]
>>> list(itertools.permutations(lst, 3))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

Endret 6. november 2012 av SNIPPSAT

[EvenAug]

Det er ikke så vanskelig... før jeg gir deg fasiten kan jeg fortelle deg fremgangsmåten:

 

Start i bakerste tallet. Hvis det er større enn den nest siste, så bytter disse plass. Hvis ikke leter du videre fremover til du finner et som er mindre enn det bakerste. Deretter bytter du plass på bakerste og den du fant. Så SNUR du rekkefølgen på ALLE tallene som er til høyre for den posisjonen den bakerste havnet i.

 

Så kommer fasiten i java:

public static int[] nestePermutasjon(int[] a) {
int n = a.length, i = n - 2;
while (i >= 0 && a[i] > a[i+1]) i--;
if (i < 0) return null;  // a er den siste
int j = n - 1;
for (int x = a[i]; a[j] < x; ) j--; // den første større enn x
bytt(a,i,j);	// bytter om
for (j = n; ++i < --j; ) bytt(a,i,j); // snur det til høyre for i

return a;
 }

 private static void bytt(int[] a, int p1, int p2) {
int temp = a[p2]; a[p2] = a[p1]; a[p1] = temp;
 }

 

Kan f.eks kjøres med:

public static void main (String[] args) {
int[] neste = {1,2,3};

while(true) {
  for(int k : neste)
	System.out.print(k + " ");
  System.out.print("\n");

  neste = nestePermutasjon(neste);
  if(neste == null)
	break;
}
 }

 

 

Merk deg at jeg ikke har testet programmet og heller ikke optimalisert det. Så belag deg på å kanskje modifisere koden litt. Og FORSTÅ den, ikke bare ta den

 

EDIT: Lurt å forstå kode istedenfor å bruke ferdige funksjoner som f.eks er nevnt over. Når du først forstår hvordan det gjøres, så kan du begynne å ta snarveier.

 

EDIT2: Testet det og gjorde noen små endringer. Fungerer utmerket og er relativt effektiv selv med store tall.

Endret 6. november 2012 av EvenAug

[GeirGrusom]

En state machine (for å danne en generator) kan kanskje løse dette. I C kan du lage en med makroer, i C++ og D kan dette enkelt løses med templates.