Permutationen 'erfassen'

Neue Frage »

Poff Auf diesen Beitrag antworten »
Permutationen 'erfassen'
@SirJective, und andere ...


Frage, gibts ein 'besonders' geeignetes Verfahren sämtliche
Elemente einer z.B. '13 stelligen Permutation'
(Permutation der Zahlengruppen bestehend aus den 13 Zahlen
zw. 1 und 13, z.B. mit Pi =(7,8,9,10,11,12,6,5,4,3,13,2,1)
programmiertechnisch SICHER und zudem möglichst EINFACH
(Speed) zu 'erfassen' ??

... wenn man z.B. sämtliche Elemente einer bestimmten Prüfung
unterziehen will, sichergehen will dass keines übersprungen wird
und zudem möglichst effizient die Elemente durchwandern will ...

Das Pi von oben sollte ein Beispielelement sein (nur der Form wegen)

P={(p1,p2,....,p13) | pi e {1,2,3,.....,13}, ((pi<>pj)) }

(pi<>pj bei einem fixen Element versteht sich ja von selbst)


verwirrt
SirJective Auf diesen Beitrag antworten »

Du möchtest also alle Elemente der S_n auflisten.
Ich hab da mal in PASCAL eine Funktion geschrieben, der man die aktuelle Permutation übergibt, und die die lexikalisch nächste liefert. Muss sie mal raussuchen...
Mazze Auf diesen Beitrag antworten »

ein sehr billiges verfahren wäre eine 13fache Zählschleife und die zählvariablen in das Feld schreiben, der aufwand wäre dann leider , aber du würdest nicht überprüfen müssen ob doppelte vorkommen weil das nicht der fall ist ; ).

Ich kann mir vorstellen das in Knuth's 3Band was interessantes dazu steht oder im Cormen - Introductions to algorithms

Das übel is das diese Bücher nich die billigsten sind aber den Cormen werd ich mir wohl auf jeden fall zulegen

hm zu surjectives methodik

Naja du würdest dann die 123...13 permutation als start wert geben, wenn die funktion so funktioniert wie ichs mir denke hast du 13! mal diese funktion auszuführen, denn du brauchst ja ALLE permutationen, also entsprechen alle lexikographischen erhöhungen. die frage ist jetzt was die methode selber für einen aufwand hat, sind keine schleifen drin kannste den aufwand konstant sehen sind doch welche drin müsste man den auch noch überprüfen, isses gar rekursiv darfste master theorem ansetzen ^^. aber für konstanten aufwand wäre seine methodik schneller.

edit

Das problem an der permutationsgeschichte ist das DU

1. alle haben willst, du kommst nicht umhin jede permutation min. einmal anzufassen, da jede verschieden ist, ergo musst du mindesten n!
mal in das feld oder wo auch immer du sie haben willst speichern
2. du nach nicht zählenden algorithmen überprüfen musst ob doppelte vorhanden sind (bei jectives und meiner methode nicht möglich)

Ich habe mir überlegt ob man das problem per divide and conquer reduzieren kann dürfte aber nicht möglich sein traurig
Wenn du von 0 anfängst wirst du wohl oder übel alle n! permutationen berechnen müssen, wie sonst willst du sie haben wenn nicht so?
Leopold Auf diesen Beitrag antworten »

Schaut einmal nach bei
http://www.matheboard.de/thread.php?thre...448&page=2&sid=

Da habe ich so etwas für Visual Basic
SirJective Auf diesen Beitrag antworten »

War doch nicht Pascal, sondern Java.
Ich hoffe, ihr versteht's.

Ob das jetzt besonders effizient ist, müsst ihr entscheiden. Für meine Zwecke war es stets ausreichend.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
/*
 * Liefert eine Permutation nach der anderen.
 * Christian Semrau, [URL]http://chsemrau.de[/URL]
 */
public class Perm{
/**
 * Liefert die lexikalisch naechste Permutation zu <code>curr</code>.
 * Wenn das bereits die letzte war, wird <code>null</code> geliefert.
 * Funktioniert auch, wenn die Elemente des Feldes nicht paarweise
 * verschieden sind.
 */
public static int[] nextPerm(int[] curr) {
	if (curr == null || curr.length<=0)
		return null;
	int[] next = (int[]) curr.clone();

	//Ende auswaehlen
	int marker = curr.length - 1;

	//solange nach vorn wandern, bis der Vorgaenger kleiner ist
	while (marker > 0 && curr[marker - 1] >= curr[marker])
		marker--;

	//wenn keiner mehr da ist, dann war das die letzte Permutation
	if (marker <= 0)
		return null;

	//diesen kleineren Vorgaenger auswaehlen
	marker--;

	//aus allen Nachfolgern den kleinsten auswaehlen, der groesser ist
	int neu = marker + 1; // garantiert groesser
	for (int h = next.length - 1; h > marker; h--)
		if (next[h] > next[marker] && next[h] < next[neu])
			neu = h;

	//tauschen
	int tmp = next[neu];
	next[neu] = next[marker];
	next[marker] = tmp;

	//die Nachfolger aufsteigend sortieren:
	//Indizes einschliesslich marker+1 und next.length-1
	sort(next, marker + 1, next.length - 1);

	//fertig
	return next;
}

/**
 * Sortiert die Elemente <code>le</code> bis <code>re</code>
 * (beide einschliesslich) von <code>feld</code>.
 * (Insertion-Sort, fuer diesen Zweck aufgrund kleiner Feldgroessen
 * ausreichend)
 */
public static void sort(int[] feld, int le, int re) {
  if (feld==null) return;
  if (le<0) le=0;
  if (re>=feld.length) re=feld.length-1;
  if (le>=re) return;

  for (int i = le+1; i <= re; i++){
	int marker = i;
	int temp = feld[i];
	while (marker > le && feld[marker - 1]>temp) {
	  feld[marker] = feld[marker - 1];
	  marker--;
	}
	if (marker!=i) {
	  feld[marker] = temp;
	}
  }
}
}
Mazze Auf diesen Beitrag antworten »

naja Leopold, hie rgehts wohl um Aufwand, also möglichst effektiv zu programmieren, und so wie sich der thread ließt scheint dein Code sämtliche möglichkeiten durchzurechnen

ergo für die eingabe länge n berehcnet dein algorithmus n! möglichkeiten

A(n) = n!

das is nur grob abgeschätzt da ich dein algorithmus nich kenne aber wenn du alle möglichkeiten expliziet berechnest das ist n! die untere Schranke der Aufwandsfunktion!

hm du ahst also 2 Schleifen drin
Beim aufwand geht man immer vom worst case aus! entpsrechend würde deine while schleife im worst case n mal über das Feld gehen

=> aufwand n
die zweite schleife is lediglich für das sortieren hat also mit der berechnung erstmal nichts zu tun

Um an alle elemente ranzukommen würde nach deiner Methode ein aufwand von

A(n) = n*n! im worst case auftreten, jetzt könnt ihr ja abschätzen ob oder n*n! stärker wächst!
 
 
Poff Auf diesen Beitrag antworten »

.... erstmal Ddankee.


Das 'Problem' ist nicht, dass ich keine Lösung oder keine Idee
gehabt hätte wie da evtl ranzugehen, sondern es geht mehr
um Effizienz, um möglichst gutes Vermeiden überflüssiger
Sequenzen Abfragen und Sonstigem.

Speicherplatz ist kein Thema, die Elemente werden 'On the Fly'
verarbeitet und sind dann ERLEDIGT.

Völlig klar ist, dass jedes Element mindestens 1 mal angefasst
werden muss, und damit ist erstmal ein nicht unterschreitbares
'Minimum' definiert.

Zum anderen gibt es aber verschiedene Möglichkeiten wie man
jeweils zum 'nächsten' Element kommen kann und dieser Weg
muss ja GENAUSO oft durchlaufen werden wie es verschiedene
Elemente gibt (mal unterstellt der Weg sei 'konstant')

Es ist also klar, dass dies ELEMENTAR für die Gesamtrechenzeit
ist und es hätte ja sein können, dass es evtl einen besonders
prädestinierten Weg gibt, wie z.B. bei Sortierungen oder
sonstigen Dingen mitunter ....


smile
Mazze Auf diesen Beitrag antworten »

Die richtig cleveren algorithmen sind sehr abstrakt, und meistens hamse augenscheinlich nicht mehr viel mit dem problem zu tun, hab ich schon oft gesehn : ).

mir ist leider noch kein genialer algorithmus für permutationen unter die augen gekommen traurig


http://schulinformatik.at/fachdidaktik/p...n-rekursion.htm

Schau dir das mal an, offensichtlich eignet sich ne baumstruktur ums zu vereinfachen, bin nur kurz drüber geflogen
SirJective Auf diesen Beitrag antworten »

Wenn du mit einem rekursiven Algorithmus klar kommst, Poff, dann funktioniert auch folgendes, und das ist mit das schnellste, was ich mir vorstellen kann:

(EDIT - Komplettes Programm mit Zählern eingefügt. Siehe einige Beiträge weiter unten.)
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
var
  f:longint; {Funktionsaufrufe}
  p:longint; {Schleifendurchlaeufe}
  pe:longint; {fertige Permutationen}

procedure permutiere(anzahl:integer);
var
  permutation: array[1..100] of integer; {feste Obergrenze}
  verwendet: array[1..100] of boolean; {geht in Pascal nicht anders}

  procedure rek(stufe:integer);
  var
    i:integer;
  begin
    inc(f); {ein Aufruf}
    if stufe=anzahl then begin
      inc(pe); {eine Permutation fertig}
    end else begin
      for i:=1 to anzahl do begin
        inc(p); {ein Schleifendurchlauf}
        if not verwendet[i] then begin
          verwendet[i]:=true;
          permutation[stufe]:=i;
          rek(stufe+1);
          verwendet[i]:=false;
        end;
      end;
    end;
  end;

var
  i:integer;
begin
  for i:=1 to anzahl do verwendet[i]:=false;
  {Initialisation nicht mitgezaehlt}
  rek(1);
end;

var
  i:integer;
begin
  for i:=1 to 10 do begin
    f:=0; p:=0; pe:=0;
    permutiere(i);
    writeln('anzahl=',i,', funktionen=',f,', schleifen=',p,', perm=',pe);
  end;
end.


Wird die Idee klar? Der Trick ist, nicht die verbleibenden Zahlen als Liste zu übergeben, oder jede Zahl darauf zu testen, ob sie von allen vorigen verschieden ist, sondern in einem Bitfeld zu sagen, welche Zahlen noch "frei" sind.

Wenn es auf die Reihenfolge derr Permutationen nicht ankommt, findet man vielleicht einen Weg, sie so anzuordnen, dass von einer zur nächsten nur je eine Transposition nötig wird. Hab aber keine Ahnung, welche Reihenfolge das für ein allgemeines n wäre. Aber darüber gibt's bestimmt auch schon Untersuchungen.

Gruss,
SirJective
Poff Auf diesen Beitrag antworten »

Ja, hab ich verstanden und auch sofort gesehen worauf du
rauswillst, da hatte ich noch nicht gesehen dass auch noch ein
erklärender Text unten nachfolgt .... *g*

automatische Verknappung der Angebotsmenge, anstatt auf
andere Art abzufragen und Co.

'Sowas' schwebte mir auch vor.

Nur, wenn ich das richtig sehe produziert das 'permutiere' beim
Aufruf ein Element für das gegeben ist, dass alle Stellen
verschieden sind und das dann an Ort und Stelle auch gleich
verarbeitet werden kann aber sonst scheint mir das noch nichts
weiter intelligentes am Hals zu haben .... Augenzwinkern
(scheinen noch ein paar 'Lücken' drin, aber darum gehts mal nicht)
...



Sag mal, zyklische Gruppen sind das keine, diese Permutationen ??


smile



... nein, ich sehe gerade das scheint schon das ganze Möglichkeiten-
feld durchzulaufen entsprechend einer 'anzahl'-fachen verschachtelten
Schleife, kann ich aber nicht ganz klar sehen, hab da etwas Probs
mit den Begin-End Zuordnungen und auch etwas mit der Pascal-Syntax.

.... so machts aber schon mehr Sinn . Augenzwinkern Augenzwinkern
Irrlicht Auf diesen Beitrag antworten »

Die symmetrischen Gruppen sind mit Ausnahme der S_1 und der S_2 nicht zyklisch. Die anderen S_n werden von 2 Elementen erzeugt, aber ich glaube nicht, dass es hier hilfreich ist.
Mazze Auf diesen Beitrag antworten »

kannst du mal "anzahl" in deinem code näher spezifizieren? Sollte anzahl die anzahl der möglichkeiten liefern ist der Algorithmus superexponentiel im wachstum und nicht zu gebrauchen!
SirJective Auf diesen Beitrag antworten »

Mazze:

Soweit ich Poffs Problem verstanden habe, sucht er nach einem schnellen Algorithmus, um sich alle Permutationen der Zahlen von 1 bis n liefern zu lassen. Da das genau n! Stueck sind, hat jeder Algorithmus eine Laufzeit, die mindestens in der Groessenordnung O(n!) liegt - es sei denn, du findest eine Moeglichkeit, laengere Permutationen schneller als kuerzere Permutationen zu liefern (als Zeit pro Permutation).

Mein iterativer Algorithmus hat eine Laufzeit von O(n! * n * log(n)), wenn man die Insertionsort durch eine O(n * log(n))-Sortierung ersetzt.

Mein rekursiver Algorithmus hat eine Laufzeit von O(n! * n). Der Parameter "anzahl" in meinem Code ist gerade dieses n, die Anzahl der zu permutierenden Zahlen.

Gruss,
SirJective
Mazze Auf diesen Beitrag antworten »

hm also n gleich die anzahl der permutierenden Zeichen

also O(n!*n) ist er sicher nicht. Folgendes, sofern der Rekursionsanker nicht erfüllt ist wird eine zählschleife aufgerufen.Die Zählschleife zählt immer bis n, dabei ist egal was sie macht, die Takte werden trotzdem verbraucht. Eine zählschleife die nichts macht sondern nur zählt hat bereits den aufwand n. Sollte die Bedingung in der Schleife nicht erfüllt sein springt er in die rekursion. Wie man sieht wird genau (n-1) mal die rekursion aufgerufen. In jeder rekursionstufe der (n-1) rekursionen wird die zählschleife VOLL durchgezählt, das kostet zeit auch wenn nichts passiert.

die zählschleifen sind verschachtelt, da du den besetzt wert immer wieder auf false setzt nach der rekursion, muss also auch die (n-1)te Schleife einen rekursionsaufruf beinhalten.
Effektiv geht dein algorithmus n-1 geschachtelte schleifen n mal durch
das müsste sein
SirJective Auf diesen Beitrag antworten »

Ich hab jetzt die Methode zu einem kompletten Programm ergänzt.

Die Methode tut genau was ich vorhergesagt habe, mit genau der Laufzeit, die ich vorhergesagt habe.
Ich zähle hier die Anzahl der Funktionsaufrufe und die Anzahl der Schleifendurchläufe. (Zähler pe liefert die Anzahl der Permutationen, die ist wie erwartet gleich .)

Für die Anzahl n von 1 bis 10 hab ich's durchlaufen lassen, und das Ergebnis, was mich selbst ein bisschen überrascht hat, ist:
Die Anzahl der Funktionsaufrufe (Zähler f) ist gleich .
Die Anzahl der Schleifendurchläufe (Zähler p) ist gleich .
Dabei ist [.] die Gaußklammer (Abrundung).

Damit ist - wenigstens in diesem Bereich - die Laufzeit von der Ordnung O(n!*n).

Mazze, du übersiehst, dass die zweite Schleife ihrerseits die Funktion nur n-2 mal aufruft, und die dritte Schleife nur n-3 mal etc.
Poff Auf diesen Beitrag antworten »

@SirJective,

wenn das so ist wie du schreibst, --was ist stark annehmen will--,
dann erscheint mir das 'optimal' ... Augenzwinkern


was ist denn bitte dieses 'e' bei der 'Laufzeitabschätzung' ?


smile
Irrlicht Auf diesen Beitrag antworten »

Augenzwinkern
Mazze Auf diesen Beitrag antworten »

hm , jetzt muss ich mich aber lansgam doch sehr wundern...

ungeachtet von dem was passiert mal durchgehen


Zustand 1:

stufe=1; anzahl= 5;
stufe != 5
Zählschleife #1 startet durchlauf mit 1
da bedingung bereits beim ersten mal erfüllt
=> Sprung in rekursion
stufe=2; anzahl = 5
stufe != 5
zählschleife startet durchlauf mit 1
bedingung nicht erfüllt
zählschleife +1 //zählt effektiv n mal durch
bedingung erfüllt
sprung in rekursion // ruft aber nur n-1 mal auf

hm effektiv wird 1 ja nicht mehr geprüft für die Oberschleife, das heißt tatsächlich das genau ein Durchlauf nicht mehr getan werden muss. Das zieht sich dann runter bis ans ende.

=>n*(n-1)*(n-2)...(n-(n-1)) hoffe das is jetzt richtig -.-
Die vorletze muss folgerichtig nur noch einmal aufrufen
Ich frag mich nur noch wieso n*(n-1) ... *(n-(n-1)) lineare resultate liefert ...

edit

ehm was ich hier beschrieben hab is n! das sind die aufrufe :P

so jetzt bin ich aufeinmal schneller als du was hab ich nu vergessen? -.-
Poff Auf diesen Beitrag antworten »

Irrlicht Thanks ....

ich weiß zwar nicht wie das da rein kommt, ist mir ehrlich gesagt
aber auch egal ...


Augenzwinkern
SirJective Auf diesen Beitrag antworten »

Ähm... ich muss das Programm doch nochmal anschauen... irgendwas scheint da immer noch nicht zu stimmen!

Mazze, was meinst du mit "lineare resultate"?

Momentan sieht es so aus:

Die Anzahl der Funktionsaufrufe erster Stufe ist gleich 1.
Die Anzahl der Funktionsaufrufe zweiter Stufe ist gleich n.
Die Anzahl der Funktionsaufrufe dritter Stufe ist gleich n*(n-1).
...
Die Anzahl der Funktionsaufrufe k-ter Stufe ist gleich n*(n-1)*...*(n-(k-2)).
...
Die Anzahl der Funktionsaufrufe (n-1)-ter Stufe ist gleich n*(n-1)*...*3.
Die Anzahl der Funktionsaufrufe n-ter Stufe ist gleich n*(n-1)*...*2.

Die Anzahl aller Funktionsaufrufe ist die Summe all dieser. Diese Zahl kann man auch als

schreiben. Die zu (e-1) fehlenden Summanden sind anscheinend in Summe kleiner als 1/n!.
Tim69 Auf diesen Beitrag antworten »

würde gerne mal hierauf noch verweisen:
http://marknelson.us/2002/03/01/next-permutation/

demnach ist die rekursive variante nicht die schnellste, die andere habe ich allerdings noch nicht verstanden. hat wohl was mit zeigern zu tun ...
nikorama Auf diesen Beitrag antworten »
permutationen erzeugen
Ich habe die Vefahren hier mal zusammengefasst:

- Permutationen erzeugen -

I) Permutationen per Rekursion erzeugen
Probleme die saemtliche Kombinationen von Zustaenden erfordern, werden
natuerlicherweise rekursiv behandelt. Dieses Vorgehen ist sehr effizient.
Allerdings ist die Erzeugung der Daten mit dem Suchbaum stark verwoben.

Ein guter Ansatz besteht darin die Eingabe-Liste zu rotieren, um jedes
Element genau einmal zu verwenden:
### permutationen_von {1,2,3}
=== 1+ permutationen_von {23}
=== 2+ permutationen_von {31}
=== 3+ permutationen_von {12}

Sollen die Permutationen sortiert vorliegen, darf man nicht rotieren:
### permutationen_von {1,2,3}
=== 1+ permutationen_von {23}
=== 2+ permutationen_von {13}
=== 3+ permutationen_von {12}

'****** Codebeispiel in Basic: rekursiver Ansatz mit Rotation *****
perm "result= " , "abc" 'start Permutationen
SUB perm (l$, r$)
IF LEN(r$) < 1 THEN PRINT l$ 'ende der rekursion? -> Ausgabe
FOR i = 1 TO LEN(r$) 'fuer alle elemente in r$
perm l$+LEFT$(r$,1) , MID$(r$,2) 'rekursion
r$ = MID$(r$,2) + LEFT$(r$,1) 'rotiere string r$
NEXT
END SUB
'******************************************************************

II) Permutationen iterativ erzeugen
Ein alternativer Ansatz besteht darin, die Permutationen in eine lexikalische
Ordnung zu bringen. Der Vorteil dieser Loesung besteht darin, dass sie es
erlaubt allein anhand der Daten auf den Nachfolger zu schliessen.

Beschreibung:
Sortiert man eine Ziffernfolge 123-132-213-231-312-321 ergibt sich eine
natuerliche Ordnung durch den Zahlenwert der Kombinationen. (An sich ist
es egal ob man Buchstaben oder Ziffern sortiert aber mit Zahlen ist es
leichter nachzuvollziehen). Wie man sieht, ergibt sich eine Umkehrung der
Sortierung (genauer: der Algorithmus sortiert von rechts nach links
aufsteigend) also wird z.B. aus abc-acb-bac-bca-cab-cba

Vorgehensweise: --------------------------- 1432 ecfdba 123 132
1. pruefe sortierung (von re nach li) ----- -432 --fdba --3 -32
2. umbruch bei ---------------------------- 1--- -c---- -2- 1--
3. naechstgroesserer Wert aus rechter liste ---2 ---d-- --3 --2
4. tausche -------------------------------- 2431 edfcba 132 231
5. sortiere rechte liste (reverse) -------- 2134 edabcf 132 213

Codebeispiel:
Eine Implementierung in Java gibt es von sirJective auf der Seite
Permutationen 'erfassen'

Die Funktion next_permutation() ist eine Variante in C++
http://www.c-plusplus.de/forum/viewtopic...-is-178286.html
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »