Algorithmus für Permutation o. Whlg. o. Reihenfolge
Neue Frage »

12.10.2006, 10:29 bjoern_krueger Auf diesen Beitrag antworten »
Algorithmus für Permutation o. Whlg. o. Reihenfolge
Moiiin!

Ich suche einen Algorythmus der mir alle Permutationen einer Zahlenreihe berechnet.

Dabei soll die Reihenfolge keine Rolle spielen, und auch Wiederholungen dürfen nicht auftreten.

Ich möchte also z.B. alle Möglichkeiten haben, aus 10 Zahlen 5 auszuwählen

Die Anzahl der möglichen Permutationen berechnet sich demnach mit
n über k (n=anzahl der herausgenommenen Elemente, k=Anzahl der Elemente, aus denen n Elemente herausgenommen werden)

Ich benötige aber nicht die ANZAHL, sondern die Permutationen selbst.

Der Algorythmus soll n sowie die Zahlenreihe abfragen. Ist nicht so wichtig, in welcher Form die Zahlenreihe abgefragt wird, das bau ich mir dann schon zurecht. Von mir aus kann die Zahlenreihe auch 'fest verdrahtet' sein.

Kann mir einer einen Algorythmuss nennen, der das macht? Muss es doch in den weiten des Internet irgendwo schon geben.

Danke und viele Grüße,

Björn
12.10.2006, 10:39 Dual Space Auf diesen Beitrag antworten »
RE: Algorythmus für Permutation o. Whlg. o. Reihenfolge
Folgender Matlabcode sollte dir helfen. Versuch den Algorithmus der dahinter steckt selber zu interpretieren:

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

function P=lexperm(p)
n=length(p);
if n==1
     P=p;
else
     P=[];
     for k=1:n
          Q=lexperm([p(1:k-1),p(k+1:n)];
          P=[P;repmat(p(k),size(Q,1),1),Q];
     end
end
12.10.2006, 12:07 AD Auf diesen Beitrag antworten »

Auch wenn es um Kombinatorik geht, ist es eher eine Softwarefrage, deshalb

Verschoben

Hast du irgendeine Präferenz, was die Softwareumgebung betrifft? Dual Space hat dir einen Matlab-Vorschlag gemacht; für C oder C++ würde ich die frei verfügbare Gnu Scientific Library empfehlen, die enthält die von dir gesuchten Funktionen im Abschnitt "Permutations".
12.10.2006, 13:09 bjoern_krueger Auf diesen Beitrag antworten »

Moin!

Erstmal Danke für die Antworten!

@Arthur Dent
Ich find's schade, dass der Thread verschoben wurde, denn ich denke, wo er jetzt ist, wird ihn keiner finden. Es geht doch um Kombinatorik, und daher hatte ich ihn in den Bereich Stochastik gestellt.
Es geht mir nur um den Algorithmus selbst, nicht um irgendein Programm, dass das gewünschte Ergebnis liefert.

Die Programmiersprache, in dem der Algorithmus dargestellt wird, ist mir im Grunde egal (wenn's nicht gerade PROLOG, SMALLTALK oder LISP ist ;o)), das Umschreiben bekomme ich schon hin, glaube ich.

Letzendlich muss ich das in VBA umschreiben, denn das Ganze läuft unter Access bzw. Excel

Die von Dir angegebene GNU-Bibliothek enthält doch keinen Quellcode, oder doch?

@Dual Space
Danke für den Code-Schnippel! Aber leider verstehe ich den code nicht so recht (obwohl ich mal Informatik studiert habe...). Wie es aussieht steckt da ne schicke Rekursion drin, wenn ich mich nicht täusche.

Trotzdem vielen Dank und noch einen schönen Tag,

Björn
12.10.2006, 13:35 AD Auf diesen Beitrag antworten »

Zitat:
Original von bjoern_krueger
Ich find's schade, dass der Thread verschoben wurde, denn ich denke, wo er jetzt ist, wird ihn keiner finden. Es geht doch um Kombinatorik, und daher hatte ich ihn in den Bereich Stochastik gestellt.

Schau mal ins Forum Stochastik: Da steht auch noch ein Link auf diesen Thread, also beruhige dich.

Zitat:
Original von bjoern_krueger
Die von Dir angegebene GNU-Bibliothek enthält doch keinen Quellcode, oder doch?

Doch natürlich, sonst wäre es ja keine Gnu-Bibliothek! Augenzwinkern
Das Problem ist vielleicht eher der Umfang und die Verzahnung mit anderen Funktionen, die eine Portierung erschweren. Daher verstehe es wirklich eher als Tipp für C und C++.
Neue Frage »
Antworten »



Verwandte Themen

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


MatheBoard » Sonstiges » Bücher & Software » Programme » Algorithmus für Permutation o. Whlg. o. Reihenfolge