Kombinations-algorithmus?

Archiv Algorithmik II
1

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.

2

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

3

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 :wink: 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?

4

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. :slight_smile:

HTH

5

danke :slight_smile:

sowas ähnliches hatte ich auch, nur hat er bei mir ein paar fälle weggelassen… grml naja werds mal mit deine code abgleichen :slight_smile:

habs hinbekommen :smiley: thx