[C++] Dataset splitsen op alle mogelijke manieren

[Darkvater]

edit:
kut, ik zie net dat deze topic eigenlijk in "Software Engineering & Architecture" moet. Kan een modje hem moven?

Sorry voor de wat vage topictitel maar ik kon geen echt passende verzinnen. Het gaat om het volgende probleem (half-abstract): ik heb dataset van N elementen en die wil ik opsplitsen in X groepen. Voor elk van deze groepen bereken ik een fitness aan de hand van een bepaalde criterium en ik kies de beste uit resultaat.

Een klein voorbeeld met N = 4 en X = 3.
Alle mogelijke combinaties van N zijn de volgende (ik heb ze niet allemaal opgesomd) (4! = 24 mogelijkheden):

code:

1234
1243
1324
1423
1432
2134
2143
2314
2341
2413
2431
...

Om deze op te splitsen in X (=3) groepen zijn voor elk element C(3,2) = 3 mogelijkheden. Eg

code:

1,   2, 34
1,  23,  4
12,  3,  4
...
1,   2, 43
1,  24,  3
12,  4,  3
...

Dus de totale aantal combinaties die ik uit kan/moet proberen zijn N! * C(N-1, X-1), voor dit probleem 24*3 = 72 mogelijkheden. Dit heb ik ook geimplementeerd, en het werkt.

Maar zoals je zelf ook kan zien, wordt explodeert dit met grotere N. Bij N = 20 heb je al 2.4*10^18 alleen al permutaties en dan moet je nog combineren. Dit is duidelijk ondoenlijk veel.

Zoals je zelf ook ziet, en ik ook heb gezien heb je heel veel dubbele. Het maakt namelijk niet uit of de groep "1, 2, 34" of "1, 2, 43" is, het is dezelfde groep. Zo kan ik het totale terugbrengen naar 6. Eg

code:

12, 3, 4
13, 4, 2
14, 2, 3
23, 1, 4
24, 1, 3
34, 1, 2

N=4, X=3 was wel makkelijk met de hand, ik zie het patroon ook; maar voor N=5, X=3 kan je al groepen maken van 3,1,1 of 2,2,1 en zijn al gelijk veel meer unieke combinaties mogelijk. Volgens mij is dit trekken zonder teruglegging.

Een groep van drie:
C(5,3) = 10, blijven er 2 over, ik trek er 1 C(2,1) = 2, blijft er 1 over C(1,1) = 1. 10*1*1 = 10.
Een groep van twee:
C(5,2) = 10, blijven er 3 over, ik trek er 2 C(3,2) = 3, blijft er 1 over C(1,1) = 1. 10*3*1 = 30;
Totaal 40? Maar het maakt niks uit of ik in de eerste groep dezelfde twee trek als in de derde groep; eg 12, 5, 34 is hetzelfde als 34, 5, 12, dus misschien? delen door 2, dan blijven in groepen van twe 15 over en is het totale combinaties 25.

Ik ben niet zo'n wiskundeknobbel, ziet iemand de regelmaat? En hoe zou ik dit in C moeten doen?

[ Voor 16% gewijzigd door Darkvater op 13-05-2009 11:30 . Reden: beter voorbeeld voor N=5 ]

[MSalters]

Een handigere methode is elementen 1 voor 1 toevoegen.

Begin met 1 element: {1}
Een tweede element kan op 2 manieren worden toegevoegd: in dezelfde groep of een eigen: {12}, {1,2}.
Een derde element kan op 4 manieren worden toegevoegd: {123}, {13,2}, {1,23}, {1,2,3}
Een vierde element kan op 12 manieren toegevoed worden: {1234}, {123,4}, {134,2}, {13,24}, {13,2,4} ... {1,2,34}, {1,2,3,4}.

Op deze manier genereer je recursief alle mogelijkheden precies 1 keer.

[.oisyn]

Wat is je vraag nou eigenlijk? Wil je alles genereren of zoek je gewoon het antwoord van "hoeveel combinaties zijn er mogelijk"?

Hij zegt het er niet expliciet bij, maar het belangrijkste element van MSalters' oplossing is natuurlijk dat een nieuw element alleen bij een bestaande groep kan of zelf een nieuwe groep kan starten zolang x < X, met x het huidig aantal groepen. Je krijgt op die manier nooit dubbelen, want {2, 1} kan niet omdat je begonnen met met {1} en de 2 een nieuwe groep start, dus {1, 2}. Een andere manier om er tegenaan te kijken is dat element n altijd in groep n of lager moet zitten. De 1 zit dus _altijd_ in groep 1. De 2 kan in groep 1 of 2. De 3 in groep 1, 2 of 3 (en 3 dan natuurlijk alleen als groep 2 ook bestaat), etc.. Op die manier is het overigens ook makkelijk iteratief te doen. Je moet gewoon N tellertjes bijhouden, die voor elk element aangeven in welke groep ze staan. Die N tellers initialiseer je op {0, 0, 0, ..., 0}, en dan ga je van achteren ophogen. Als een teller hoger wordt dan de vorige teller plus 1, dan gaat ie terug naar 0 en verhoog je de vorige teller met 1 (en dan kijk je opnieuw of die vorige teller niet te hoog wordt in relatie tot de teller die daar weer voor staat, etc., totdat je de eerste teller op moet hogen, wat niet kan dus ben je klaar).

En moeten het altijd X groepen zijn, of mogen er ook minder groepen bestaan? Indien dat eerste kun je natuurlijk de optimalisatie maken dat je met nog n elementen te gaan en X-x = n dat elk element vervolgens in zijn eigen groep terecht moet komen, wat een hoop nutteloze iteraties voorkomt. Oftewel, bij N=6 en X=4 en je hebt {123} al gegenereerd, dan kan dat alleen maar resulteren in {123,4,5,6} - alle overige permutaties van 4, 5 en 6 zijn ongeldig want dan eindig je met te weinig groepen.

[ Voor 115% gewijzigd door .oisyn op 13-05-2009 23:11 ]

[Darkvater]

Dank je wel allebei...het is inderdaad veel simpeler dan ik gedacht had. Het gaat mij om dat ik alle combinaties moet hebben, uitrekenen hoeveel het er zijn lukt nog wel denk ik (vooral nu ik de structuur zie).

Ik heb nog wel een vraagje over de specifieke implementatie van .oisyn met de tellers. Als ik alles afloop heb ik op een gegeven moment:

code:

...
{0,0,1,1}
{0,0,1,2}
{0,1,0,0}
{0,1,0,1}
{0,1,1,0}
...

{0,0,1,2} flipt om naar {0,1,0,0} door het iteratief ophogen. Echter, hierdoor mis ik de combinatie {0,1,0,2} die niet meer mogelijk is na {0,1,0,1}. Mis ik iets hier of was dit je bedoeling

[MSalters]

De tellers {0,1,0,1} en {0,1,0,2} kunnen allebei, want ze komen overeen met {13,24} en {13,2,4}.

Wat .oisyn probeerde te zeggen is dat de rollover waarde voor teller T_i gelijk is aan max(T₀..T_i-1) + 1. {0,1,0,3} kan niet, 3>1+1.

[ Voor 5% gewijzigd door MSalters op 14-05-2009 16:15 ]

[Darkvater]

MSalters schreef op donderdag 14 mei 2009 @ 16:13:
De tellers {0,1,0,1} en {0,1,0,2} kunnen allebei, want ze komen overeen met {13,24} en {13,2,4}.

Wat .oisyn probeerde te zeggen is dat de rollover waarde voor teller T_i gelijk is aan max(T₀..T_i-1) + 1. {0,1,0,3} kan niet, 3>1+1.

Ja, ik weet dat ze kunnen, maar ze misten in zijn algoritme, vandaar mijn vraag
Je hebt inderdaad gelijk hierover, zo heb ik het ook opgelost.

[.oisyn]

MSalters schreef op donderdag 14 mei 2009 @ 16:13:
Wat .oisyn probeerde te zeggen is dat de rollover waarde voor teller T_i gelijk is aan max(T₀..T_i-1) + 1. {0,1,0,3} kan niet, 3>1+1.

Euh ja, dat idd. Niet T_i <= T_i-1+1