Schrift
Start · Board · Anwendungen/Programme/Skripte in Perl · Allgemeines zu Perl
[thread]10048[/thread]

Suche Algorithmus

Leser: 2


<< >> 6 Einträge, 1 Seite
mikdoe
 2007-08-13 11:18
#98021 #98021
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
#98025 #98025
User since
2003-08-04
14371 Artikel
ModeratorIn
[Homepage] [default_avatar]
Code (perl): (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#!/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 )
1
2
3
4
5
6
7
8
9
10
11
12
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/
pq
 2007-08-13 11:45
#98027 #98027
User since
2003-08-04
12209 Artikel
Admin1
[Homepage]
user image
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
#98064 #98064
User since
2003-08-14
2022 Artikel
BenutzerIn
[default_avatar]
Code (perl): (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#!/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
#98067 #98067
User since
2004-07-19
1776 Artikel
HausmeisterIn
[Homepage]
user image
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
#98068 #98068
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.
<< >> 6 Einträge, 1 Seite



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