Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Kombinations-algorithmus?
tag
kennt jemand einen algorithmus der mir alle kombinationen einen
n langen feldes ausgibt? (also n! möglichkeiten)
z.b.
n = 3 ; → 6 möglichkeiten
[0][1][2]
[0][2][1]
[1][0][2]
[1][2][0]
[2][1][0]
[2][0][1]
am besten ein mathematischer zusammenhang ohne tauschoperationen…
Drager
mathematisch gesehen suchst du die menge aller permutationen eines n-tupels. diese haben wir mit S[sub]n[/sub] bezeichnet (unterhalb des satzes 1.42).
der algorithmus ist rekursiv - die permutationen einen n-tupels werden also auf die permutationen einen n-1-tupels zurückgeführt, und danach muss noch eine geeignete operation stehen 
ich glaub, in scheme haben wir die insert () genannt (?!) der trivialfall ist der eines 1-tupels :-p
kannst du deine ansinnen vielleicht genauer erläutern?
hier noch ein paar wikipedia links:
http://www.wikipedia.org/wiki/Mathematical_group
http://www.wikipedia.org/wiki/Permutation_group
http://www.wikipedia.org/wiki/Symmetric_group
http://www.wikipedia.org/wiki/Permutation
hier also ein algorithmus “permut”:
eingabe:
ein n-tupel t=(x[sub]1[/sub], …, x[sub]n[/sub]), nεN
verarbeitung:
falls n=1, STOP, trivialfall. gib die ergebnismenge M={t} zurück.
ansonsten: nimm ein beliebiges element a - hier obda das erste - aus t heraus. dadurch entsteht ein tupel t’=(x[sub]2[/sub], …, x[sub]n[/sub]), also a=x[sub]1[/sub]. dann rufe rekursiv permut auf, und zwar mit t’ als argument. speichere die rückgabe in M. für jedes tupel mεM erzeuge eine menge M[sub]i[/sub], i=1, …, |M|. M[sub]i[/sub] entsteht durch einfügen von a an allen möglichen stellen von m - das ist die schon angesprochenen insert () operation. bilde N := ∪M[sub]i[/sub], i=1, …, |M| und gib N zurück.
ausgabe:
eine menge M, die alle permutationen von t enthält.
eine - zugegeben miese - perl implementierung:
[code]kabel@linux:~/progs/perl> cat permut.pl
use strict;
alles was keine zahl ist: raus!
my @tupel = grep {/^\d+$/} @ARGV;
my @permutations = permut (@tupel);
print “anzahl der permutationen ist [”, scalar (@permutations), “]\n”;
my $counter = 0;
foreach my $permutation (@permutations) {
print “[”, join (', ', @$permutation), “]”;
$counter ++;
print “\n” if ($counter % scalar (@tupel)) == 0;
}
sub permut {
my ($tuple_original) = @_;
my $tuple = [@$tuple_original];
my $n = scalar (@$tuple);
# in $n steht dann die anzahl der elemente im array @$tuple
# der trivialfall
return $tuple if ($n == 1);
# das erste element rausnehmen; dadurch wird die ausgabe sehr regelmässig
my $a = shift @$tuple;
# und der rekursive aufruf; die anzahl der elemente ist $n-1.
my @M = permut ($tuple);
# im array R werden die ergebnis-tupel gesammelt
my @R = ();
foreach my $m (@M) {
my $elem_count = scalar (@$m); # in $elem_count steht die anzahl elemente von @$m
# wir gehen alle möglichen einfügepositionen durch ...
foreach my $position (0 .. $elem_count) {
my @temp2 = @$m;
# ... fügen das element $a an die stelle $position in das temporäre array ein ...
splice @temp2, $position, 0, $a;
# ... und fügen es dem ergebnis-array zu.
push @R, \@temp2;
}
}
return @R;
}
kabel@linux:~/progs/perl> perl -w permut.pl 1 a 2 3 4
anzahl der permutationen ist [24]
[1, 2, 3, 4][2, 1, 3, 4][2, 3, 1, 4][2, 3, 4, 1]
[1, 3, 2, 4][3, 1, 2, 4][3, 2, 1, 4][3, 2, 4, 1]
[1, 3, 4, 2][3, 1, 4, 2][3, 4, 1, 2][3, 4, 2, 1]
[1, 2, 4, 3][2, 1, 4, 3][2, 4, 1, 3][2, 4, 3, 1]
[1, 4, 2, 3][4, 1, 2, 3][4, 2, 1, 3][4, 2, 3, 1]
[1, 4, 3, 2][4, 1, 3, 2][4, 3, 1, 2][4, 3, 2, 1]
kabel@linux:~/progs/perl>[/code]
laufzeit O(n!) :-p oh je …
ich konnte die mathematische notation leider nicht 1:1 übernehmen, die kommentare richten das aber hoffentlich. 
HTH
danke
sowas ähnliches hatte ich auch, nur hat er bei mir ein paar fälle weggelassen… grml naja werds mal mit deine code abgleichen
habs hinbekommen 
thx