Suche Algorithmus (Allgemeines zu Perl)

[thread]10048[/thread]

Suche Algorithmus

Leser: 2

mikdoe

2007-08-13 11:18

User since
2007-08-13
98 Artikel
BenutzerIn
[default_avatar]

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 Caesar
Beta Caesar
Alpha Caesar

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 Caesar
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

renee

2007-08-13 11:39

User since
2003-08-04
14371 Artikel
ModeratorIn

Code (perl): (dl )

#!/usr/bin/perl

use strict;
use warnings;
use Math::Combinatorics;

my @list = qw(Alpha Beta Caesar Delta);

for( 2 .. scalar(@list) ){
    my $comb = Math::Combinatorics->new(
        count => $_,
        data  => [@list],
    );
    
    while( my @perms = $comb->next_combination ){
        print join( ' ', @perms ), "\n";
    }
}

Ausgabe:

Code: (dl )

C:\>combinatorics.pl
Alpha Beta
Alpha Caesar
Alpha Delta
Beta Caesar
Beta Delta
Caesar Delta
Alpha Beta Caesar
Alpha Beta Delta
Alpha Caesar Delta
Beta Caesar Delta
Alpha Caesar Beta Delta

OTRS-Erweiterungen (http://feature-addons.de/)
Frankfurt Perlmongers (http://frankfurt.pm/)
--

Unterlagen OTRS-Workshop 2012: http://otrs.perl-services.de/workshop.html
Perl-Entwicklung: http://perl-services.de/

2007-08-13 11:45

User since
2003-08-04
12208 Artikel
Admin1

keine ahnung, ob es einen namen und/oder ein modul dafür gibt, aber
ich würde so vorgehen:
bei einer ein-elementigen liste hast du das ergebnis.
bei mehreren elementen kannst du das ergebnis auf eine ein-elementige liste
zurückführen. einfache rekursion.
also:
bei einer liste 1..n iterierst du über die elemente, also für jedes element r aus 1..n
fügst du der ergebnisliste (element(r), funktion(r+1 .. n)) hinzu.

Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live. -- Damian Conway in "Perl Best Practices"
lesen: Wiki:

Wie frage ich & perlintro Wiki:

brian's Leitfaden für jedes Perl-Problem

Ronnie

2007-08-13 17:40

User since
2003-08-14
2022 Artikel
BenutzerIn
[default_avatar]

Code (perl): (dl )

#!/usr/bin/perl

use strict;
use warnings;

use Data::Dumper;

my @words       = qw/foo bar buz qiz/;
my $words_cnt   = @words;

my @wanted = grep {
    @$_ >= 2;
} map {
    my $i = $_;
    [ @words[grep { $i->[$_] > 0} 0..@$i-1] ];
} map { 
    [ split //, sprintf "%0" . $words_cnt . "b", $_ ]
}  1..(2**$words_cnt-1);

warn Dumper \@wanted;

Zugegeben es ist etwas kryptisch. Die Idee dahinter ist aber einfach. Für eine Liste mit n Elementen gibt es 2^n mögliche Varianten. Diese entsprechen den 1 im Binärwert jeder Zahl von 1..n (die 0 als leere Liste ausgelassen). Also muss man nur zwei Arrays vergleichen und die Elemente zurückliefern, bei denen eine 1 im Binärwert steht.

murphy

2007-08-13 17:51

User since
2004-07-19
1776 Artikel
HausmeisterIn

Das Problem (ohne Beschränkung auf mindestens zwei Wörter pro Ausgabemenge) gab's auch mal als Rätsel der Woche: Wiki » Wissensbasis » Rätsel der Woche #2

When C++ is your hammer, every problem looks like your thumb.

Ronnie

2007-08-13 17:53

User since
2003-08-14
2022 Artikel
BenutzerIn
[default_avatar]

murphy+2007-08-13 15:51:21--
Das Problem (ohne Beschränkung auf mindestens zwei Wörter pro Ausgabemenge) gab's auch mal als Rätsel der Woche: Wiki » Wissensbasis » Rätsel der Woche #2

Stimmt, wusste das es mir bekannt vorkommt. Hatte damals sogar eine Lösung die so ähnlich funktioniert wie obige, nur habe ich damals glob missbraucht, ohne das ich noch wüsste wieso das funktioniert.

EDIT: Der Tabelle im Wiki entnehme ich das es wohl auch nicht funktioniert hat - also lohnt es sich auch nicht mehr drüber nachzudenken.

View all threads created 2007-08-13 11:18.