Algotithmus für Permutationen?

[AtWork]

Hallo!
Ich habe das folgende Problem: Bin auf der Suche nach einem möglichst schnellen Algorithmus zur Berechnung von Permutationen.
Ein Beispiel: Sei die Reihe {1,4,5,8,6,7,9} gegeben.
Die Permutation 012 kommt 3-mal vor ({1,4,5},{4,5,8},{6,7,9}), die Permutation 021 kommt 1-mal vor ({5,8,6}) und 201 kommt 1-mal vor ({8,6,7}).
Der Algorithmus sollte mir die Anzahl der Permutationen einer Sorte ausgeben, wobei die Art der "Sorte" keine Rolle spielt. Als Output würde also (3,1,1) ausreichen.
Bisher habe ich alles mit IF-Schleifen gemacht. Wenn ich aber mehr als 3 Zahlen vergleichen will, muss ich ziemlich viel tippen. Das geht bestimmt auch eleganter. Weiss jemand wie?

Vielen Dank....

[Nikolas]

Das, was du als Permutation bezeichnest, ist keine.
Könntest du vielleicht mal an einem Beispiel kurz erklären, wodurch sich die 'Permutation 012' definiert?


{

Zitat:

IF-Schleifen // ????

}

[Dust Signs]

//Sorry, falsch gedacht...

Dust Signs

[AtWork]

Ich nenne die drei zu vergleichenden Zahlen mal (x0,x1,x2). Wenn gilt x1 < x2 < x0 nenne ich die Permutation 120. Deshalb müsste der ({5,8,6}) oben auch die 120 zugeordnet werden. Mein Fehler...
Bei z.B. x2 < x0 < x1 nenne ich sie 201.
Ok?

[Nikolas]

Von dieser Einteilung von Permutationen hab ich noch nie gehört, naja, wenn du sowas auch mit längeren Auschnitten machen willst, solltest du dir eine Funktion schreiben, die dir zurückgibt, welcher Art die übergebene Folge ist. (ich geh mal davon aus, dass es sich um natürlich Zahlen handelt)

Etwa so

Delphi-Quellcode:

type
tDynIntegerArray

Function SageMirDenTyp(list: tDynIntegerArray): tdynintegerArray;
var
cnt,i,j,max,wo: integer;
begin
cnt:= length(list);
setlength(result,cnt);

for i:= 0 to cnt-1 do
begin
 max:= list[0];
 wo:=0;
   for j:= 1 to cnt-1 do
   begin
     if list[j] > max then 
     begin
     max:= list[j];
     wo:=j;
     list[j]:=0;
     end;
   end;
 result[i]:=wo;
end;

Das ist ein etwas abgewandelter Selection-Sort Algorhytmus der dir eigentlich den Typ deiner Reihe zurückgeben sollte.

[AtWork]

@ Toxman: Vielen Dank für die Mühe!. Leider funktioniert Dein Algorithmus so nicht. Habs mal ausprobiert, aber er liefert nur (000), (120) oder (100). Verbessern konnte ich es aber bisher auch nicht. Hat irgendwas damit zu tun, dass die Werte in der zweiten FOR-Schleifen auf Null gesetzt werden...

[Nikolas]

Der Code war nur so als Ansatz gedacht. Die Idee dahinter ist die vom Selectionsort, da kannst du was in den Tutorials drüber nachlesen. Ich habe ihn selbst nicht getestet.

Ich glaube aber, dass ich einen wichtigen Fehler gesehen habe.
Es sollte so etwas besser gehen:

Delphi-Quellcode:

Function SageMirDenTyp(var list: tDynIntegerArray): tdynintegerArray;
var
cnt,i,j,max,wo: integer;
begin
cnt:= length(list);
setlength(result,cnt);

for i:= 0 to cnt-1 do
begin
max:= list[0];
wo:=0;
   for j:= 1 to cnt-1 do
   begin
     if list[j] > max then
     begin
     max:= list[j];
     wo:=j;
     // list[j]:=0; Eindeutig an der falschen Stelle
     end;
   end;
result[i]:=wo;
list[wo]:=0; // Jetzt erst ist sicher, dass dieser Wert nicht mehr benötigt wird. 
end;

Natürlich besteht die übergebene List nachher nur noch aus Nullen, wenn dir das nicht gefällt, musst du noch eine Kopie erstellen.