Suche Algorithmus
am 12.08.2007 15:10:01 von info
Hi!
Das Problem ist folgendes:
Ich habe eine bestimmte Anzahl Wörter und möchte damit alle Kombinationen
bilden, die nicht auf Drehung/Permuatation sondern auf verschiedentliche
Kombination miteinander beruhen, wobei jedes Ergebnis mindestens zwei der
Wörter aus der Ausgangsliste enthalten muss.
Beispiel 1:
Ausgangsliste der Wörter: Alpha Beta Caesar
Dazu möchte ich als Ergebnis folgende Ergebnisse haben (Rangfolge ist egal):
Alpha Beta
Alpha Beta Ceasar
Beta Ceasar
Alpha Ceasar
Beispiel 2:
Ausgangsliste der Wörter: Alpha Beta Caesar Delta
Dazu möchte ich als Ergebnis folgende Ergebnisse haben (Rangfolge ist egal:
Alpha Beta
Alpha Beta Caesar
Alpha Beta Caesar Delta
Alpha Ceasar
Alpha Caesar Delta
Alpha Delta
Beta Caesar
Beta Caesar Delta
Beta Delta
Caesar Delta
Wie heißt ein solcher Algorithmus und gibt es dazu evtl. ein Modul?
Danke und Grüße
----------------
Ich weiß, dass meine Signatur nicht richtig ist, weil ich OEX nutze.
Habe aber vergessen, wie man das richtig macht.
Sorry!!!
Re: Suche Algorithmus
am 13.08.2007 09:02:47 von Christian Winter
Michael Döring schrieb:
> Hi!
>
> Das Problem ist folgendes:
> Ich habe eine bestimmte Anzahl Wörter und möchte damit alle Kombinationen
> bilden, die nicht auf Drehung/Permuatation sondern auf verschiedentliche
> Kombination miteinander beruhen, wobei jedes Ergebnis mindestens zwei der
> Wörter aus der Ausgangsliste enthalten muss.
>
> Beispiel 1:
> Ausgangsliste der Wörter: Alpha Beta Caesar
>
> Dazu möchte ich als Ergebnis folgende Ergebnisse haben (Rangfolge ist egal):
> Alpha Beta
> Alpha Beta Ceasar
> Beta Ceasar
> Alpha Ceasar
>
> Beispiel 2:
> Ausgangsliste der Wörter: Alpha Beta Caesar Delta
>
> Dazu möchte ich als Ergebnis folgende Ergebnisse haben (Rangfolge ist egal:
> Alpha Beta
> Alpha Beta Caesar
> Alpha Beta Caesar Delta
> Alpha Ceasar
> Alpha Caesar Delta
> Alpha Delta
> Beta Caesar
> Beta Caesar Delta
> Beta Delta
> Caesar Delta
>
> Wie heißt ein solcher Algorithmus und gibt es dazu evtl. ein Modul?
Du suchst alle Kombinationen von 2..n aus einer Liste der Länge n.
Math::Combinatorics ist Dein Freund.
#!/usr/bin/perl
use strict;
use warnings;
use Math::Combinatorics;
my @set = qw(Alpha Beta Caesar Delta);
foreach my $len ( 2 .. scalar(@set) )
{
for( map {join ' ', sort {$a cmp $b} @$_} combine($len,@set) )
{
print $_.$/;
}
}
-Christian