[perl]Cartesian algoritme over een 2d array

[Verwijderd]

Ik heb een vraag:

Is het mogelijk om een cartesian algoritme toe te passen op een 2d array?

Zo nee, is er een andere mogelijkheid om het wel voor elkaar te krijgen?

De reden waarom ik het vraag is omdat ik het nodig heb voor het maken van generator maar mijn kennis aangaande dit soort algoritmes te beperkt om een soort gelijke oplossing te maken.

[Soultaker]

WTF is een Cartesian algoritme?

[kwaakvaak_v2]

Ik gok een Cartasian Product. En of dat over 2d kan, dat weet ik niet.

[Verwijderd]

@Soultaker: wat kwaakvaak said.

[pedorus]

Je wilt een self join doen ofzo? Of gaat het hier om 2 arrays? Waarbij de arrays eigenlijk sets voorstellen? Wat wil je nu eigenlijk doen?

Anyways: [google=perl cartesian product]

[Verwijderd]

Wat ik precies wil doen is permutaties-combinaties op basis van waardes uit een 2D array:

Wat ik nu heb is dat ik deze array heb:

Perl:

my @steps = (
    ["b1", "1"],
    ["b2", "2", "\#2"],
    ["b3", "3", "\#3"],
    ["b4", "4", "\#4"],
    ["b5", "5", "\#5"],
    ["b6", "6", "\#6"],
    ["b7", "7", "\#7"],
);

en daar wil ik de volgende combinaties meemaken:

1 b2, 3, 4 5#, 6, 7b
1 b2, 3b, 4# 5, 6#, 7

maar ook:

1 2b 2 # 3 4# 5 5# 6 7

En dat kan blijkbaar met een aangepaste cartesian product algoritme.

[ Voor 0% gewijzigd door RobIII op 22-05-2012 21:50 . Reden: Code tags gefixed ]

[pedorus]

Dat laatste voorbeeld kan ik niet plaatsen. Je wilt 1 of meer elementen uit iedere array in de lijst selecteren? Die eerste 2 hebben ook wat komma's/tikfouten. Verder deze hit:
http://stackoverflow.com/...-product-of-multiple-sets
Math::Cartesian::Product zou werken voor de eerste 2

[Soultaker]

En als die module je niet bevalt, dan kun je het natuurlijjk ook zo zelf in elkaar hacken, met simpele backtracking:

Perl:

my @selection = ();
sub choose {
    my $index = shift;
    if ($index gt $#steps) {
        print "@selection\n"  # of iets anders
    } else {
        foreach my $step (@{$steps[$index]}) {
            $selection[$index] = $step;
            choose($index + 1);
        }
    }
}
choose 0

[pedorus]

Backtracking? Ik zie eigenlijk alleen maar recursie aangezien alles voldoet bij deze 'backtracking'

[ Voor 6% gewijzigd door pedorus op 23-05-2012 11:05 ]

[Soultaker]

Recursief is 'ie sowieso. Ik noem het backtracking omdat je de deeloplossingen die je in de ene iteratie gegenereerd hebt voor de volgende weer weggooid. Als je vindt dat essentieel onderdeel van backtracking is dat sommige deeloplossingen niet tot eindoplossingen leiden, dan is het niet echt backtracking inderdaad. Vanuit het perspectief van de recursieve functie maakt het natuurlijk weinig uit of de recursieve aanroepen wel of niet tot een oplossing leiden; in die zin zit er weinig verschil tussen backtracking en wat jij niet-backtracking noemt.

[ Voor 31% gewijzigd door Soultaker op 23-05-2012 16:36 ]