[Løst] Algoritme for utvalg av elementer fra en mengde

[alfred97]

Er ute etter en algoritme for å løse følgende problem.

 

Jeg har en mengde på N elementer, og fra denne mengden ønsker jeg å finne alle mulige utvalg av x elementer.

 

For eksempel, hvis startmengden er {1,2,3,5,8} og x=3, vil jeg ende opp med en liste som dette:

{1,2,3}

{1,2,5}

{1,2,8}

{1,3,5}

{1,3,8}

... og så videre.

 

Jeg er ute etter et uordnet utvalg - det vil si at {1,3,8} betraktes som identisk med f.eks. {8,1,3}.

 

Noen som har gode tips om hvordan man kan implementere noe slikt på en elegant, lesbar og ytelsesmessig forsvarlig måte?

[Topguy]

Det virker jo logisk å tenke seg en rekursiv funksjon. f.eks F(x, list1, list2).

 

"x" er ønsket antall elementer, "list1" inneholder alle elemente plukket ut, "list2" inneholder de som ikke valgt.

 

Så lenge antallet elementer i list1 < x så velger man seg neste element ifra list2, flytter det ifra "list2" til "list1" og så kaller funksjonenen seg selv. Er antallet elementer i list1 = x så skriver du ut elementene i listen og returnerer.

 

F(3,{},{1,2,3,5,8})->F(3,{1},{2,3,5,8})->F(3,{1,2},{3,5,8})->F(3,{1,2,3},{5,8})
                                                         -> F(3,{1,2,5}, {8})
                                                         -> F(3,{1,2,8}, {})
                                  	-> F(3,{1,3}, {5,8}) -> F( 3,{1,3,5},{8})
                                                         -> F(3,{1,3,8}, {})

og så videre....

Endret 8. april 2011 av Topguy

[zotbar1234]

Jeg har en mengde på N elementer, og fra denne mengden ønsker jeg å finne alle mulige utvalg av x elementer.

 

Altså, gitt en mengde, ønsker du å generere alle mulige delmengder av en gitt størrelse.

 

Jeg er ute etter et uordnet utvalg - det vil si at {1,3,8} betraktes som identisk med f.eks. {8,1,3}.

 

Jepp.

 

Noen som har gode tips om hvordan man kan implementere noe slikt på en elegant, lesbar og ytelsesmessig forsvarlig måte?

 

La oss ta ytelsesmessig først. Algoritmen vil nødvendigvis være nedad begrenset av N \choose x, siden det er størrelsen av svaret. Den biten får man ikke gjort noe med (combination hos mathworld). Dvs. du bør ikke anvende dette på store mengder uansett

 

Tilbake til algoritmen.

 

Jeg synes det er nyttig å tenke på slik genering rekursivt: for hvert neste element E, består svarmengden av de delmengdene (med x elementer) der E er med samt de delmengdene der E ikke er med. Disse kan genereres med rekursive kall, der hver rekursiv kallkjede returnerer "neste" delmengde i svaret. Underveis må du holde rede på hvor mange elementer allerede er med i det neste svaret og du stopper de rekursive kallene såsnart du har det rette antall (Python sin "yield" er veldig nyttig her).

Endret 8. april 2011 av zotbar1234

[alfred97]

Gode innspill, folkens - dette kan jeg trolig bruke. Takker så meget!

[snippsat]

Itertools er en build-in module i python med mye stryke.

For en oppgave som dette kan det finnes en enkel løsning.

Som du ser i doc "Equivalent to" hvordan koden er bygd opp.

 

For din oppgave passer itertools.combinations bra.

Kan ta det ned på en linje med og bruke list,list kaller da alle kombinasjoner i

generator object som itertools.combinations lager.

 

>>> import pprint
>>> pprint.pprint(list(itertools.combinations([1,2,3,5,8], 3)))
[(1, 2, 3),
(1, 2, 5),
(1, 2, 8),
(1, 3, 5),
(1, 3, 8),
(1, 5, 8),
(2, 3, 5),
(2, 3, 8),
(2, 5, 8),
(3, 5, 8)]
>>> 

Endret 9. april 2011 av SNIPPSAT