Hovedbrud, parvis samling

Tags:    php algortime permutationer

Denne her har jeg vist fået stirret mig blind på.

Jeg har et samling bestående af 3 x 2 bogstaver, altså: AB CD og EF

Disse sæt skal jeg have kombineret til nedestående resultat via en fornuftig algoritme:

ACE
ACEF
ACDE
ACDEF
ABCE
ABCEF
ABCDE
ABCDEF

Antallet af resultater vil altid være 2 ^ 3, og hvis det var en samling af 4 x 2 bogstaver vil det være 2 ^ 4.
Altså i princippet er det permutationer, dog uden at permutation kan ske vilkårligt.

Er der nogen der kender til en løsning af ovenstående?



3 svar postet i denne tråd vises herunder
2 indlæg har modtaget i alt 10 karma
Sorter efter stemmer Sorter efter dato
Hvis hvert sæt (AB,CD,EF,..) kun kan antage 2 værdier (f.x. A og AB), så er det oplagt at bruge det binære system.

000 til 111 kan repræsentere alle permutationerne.

000 = ACE
001 = ACEF
010 = ACDE
011 = ACDEF
..
111 = ABCDEF

Så tag udgangspunkt i antal = 2^3, gennemløb alle kombinationer, omsæt til binær og plot resultaterne sammen.

Forslag til kode:

Fold kodeboks ind/udPHP kode 





Indlæg senest redigeret d. 15.03.2012 12:44 af Bruger #955
En alternativ implementering af Stefans ide om den binære repræsentation af permutationerne.

Fold kodeboks ind/udPHP kode 


Fordelen er umiddelbart at den virker uanset hvor mange elementer der er i dit input array. Og så synes jeg det virker mere logisk at bruge array_map :)



Indlæg senest redigeret d. 15.03.2012 15:23 af Bruger #17015
Tak skal i have... det giver mening, når man lige anskuer det på en anden måde. :)



t