[PHP] Algorithme om unieke combinaties te bepalen

[Donderpoes]

Ik loop stuk om een manier te vinden die unieke combinaties maakt van een x aantal termen, waarbij er steeds meer termen afvallen. Bijv: ik heb 5 termen, 1, 2, 3, 4, 5

De eerste combinatie is 12345
Hierna valt er steeds 1 term weg:
1234 - 5
1235 - 4
1245 - 3
1345 - 2
2345 - 1

Hierna vallen er 2 weg
123 - 45
124 - 35
125 - 34
134 - 25
135 - 24
145 - 23
234 - 15
235 - 14
245 - 13
345 - 12

De termen die wegvallen vormen tegelijkertijd ook een unieke combinatie.

Stel ik heb 6 termen en er vallen er 3 weg, dan vormen de wegvallende termen de andere helft van de combinaties met 3.

123 - 456
124 - 356
125 - 346
126 - 345
134 - 256
135 - 246
136 - 245
145 - 236
146 - 235
156 - 234

Wat ik hieraan over wil houden is een array met alle mogelijke unieke combinaties.

Ik kom er zelf momenteel niet helemaal uit om dit te maken. Ik heb een begin gemaakt, maar dit wordt veel te omslachtig. Kan iemand mij misschien een schopje in de goede richting geven?

PHP:

$terms = array('term1','term2','term3','term4','term5');
$number_of_terms = count($terms);
$array = array();
for($a=0;$a<$number_of_terms;$a++) {
    if($a == 0) { 
        //alles
        $array[] = implode('',$terms);
        // done = x termen
    } else if($a == 1) {
        for($b=($number_of_terms-1);$b>=0;$b--) {
            $tmp_terms = $terms;
            unset($tmp_terms[$b]);
            $array[] = implode('',$tmp_terms);
            $array[] = $terms[$b];
        }
        // done = 1 term, x termen
        // todo = 2 en x termen
    } else if($a == 2) {
        // 2 en x termen
    }
}

[HuHu]

Wat je wilt heet k-combinations: Wikipedia: Combination Dat maakt 't zoeken wellicht wat makkelijker.

Voorbeeld: http://stackoverflow.com/...ions-of-k-elements-from-n

[Donderpoes]

Handige link, ik ga het even lezen. Dat is inderdaad wat ik bedoel.

Ik had overigens wel een kant en klare code gevonden, maar dan leer ik er zelf niet veel van.

[Soultaker]

Je kunt die combinaties vrij makkelijk recursief opbouwen, door voor elke term afzonderlijk te bepalen of je 'm in je huidige combinatie meeneemt of juist niet.

Voorbeeldje in Python:

Python:

terms = [1,2,3,4,5]
taken = [0,0,0]

def combine(i, j):
  if j == len(taken):
    print(taken)
  elif i < len(terms):
    taken[j] = terms[i]
    combine(i + 1, j + 1) # take i-th term
    combine(i + 1, j)     # drop i-th term

combine(0, 0)

[Morrar]

HuHu schreef op maandag 28 juli 2014 @ 12:46:
Wat je wilt heet k-combinations: Wikipedia: Combination Dat maakt 't zoeken wellicht wat makkelijker.

Voorbeeld: http://stackoverflow.com/...ions-of-k-elements-from-n

Is hierbij niet de restrictie dat de elementen oplopend zijn / dat de ordening niet uitmaakt? Dus 123 en 234, maar niet 132 of 324 (omdat deze dezelfde elementen bevatten, maar dan in andere volgorde)?

Ik weet niet welke restricties de TS in gedachte had? Gaat het alleen om unieke combinaties of zijn er andere restricties? Het 'weg laten vallen' suggereert dat de elementen in ieder geval in dezelfde ordening moeten blijven staan, minus een of meerdere elementen.

[ Voor 6% gewijzigd door Morrar op 28-07-2014 13:30 ]

[HuHu]

Morrar schreef op maandag 28 juli 2014 @ 13:28:
[...]


Is hierbij niet de restrictie dat de elementen oplopend zijn / dat de ordening niet uitmaakt? Dus 123 en 234, maar niet 132 of 324 (omdat deze dezelfde elementen bevatten, maar dan in andere volgorde)?

Ik weet niet welke restricties de TS in gedachte had? Gaat het alleen om unieke combinaties of zijn er andere restricties? Het 'weg laten vallen' suggereert dat de elementen in ieder geval in dezelfde ordening moeten blijven staan, minus een of meerdere elementen.

Unieke combinaties (waarbij elk element maar éénmaal voor komt, dus 123=132=213=231=312=321) kun je eenvoudig achteraf sorteren.

[Donderpoes]

Bedankt mensen. Ik heb mijzelf ingelezen en ik snap het nu

Een handig stukje wat ik ook ben tegen gekomen: http://r.je/php-find-every-combination.html

Morrar schreef op maandag 28 juli 2014 @ 13:28:
[...]


Is hierbij niet de restrictie dat de elementen oplopend zijn / dat de ordening niet uitmaakt? Dus 123 en 234, maar niet 132 of 324 (omdat deze dezelfde elementen bevatten, maar dan in andere volgorde)?

Ik weet niet welke restricties de TS in gedachte had? Gaat het alleen om unieke combinaties of zijn er andere restricties? Het 'weg laten vallen' suggereert dat de elementen in ieder geval in dezelfde ordening moeten blijven staan, minus een of meerdere elementen.

Mijn restrictie is dat de combinaties uniek moeten zijn uit de termen die de combinatie bevatten. Als ik 123 heb dan wil ik niet 231 hebben.
Aan elke combinatie hang ik een gewicht. Hoe meer woorden in een combinatie hoe zwaarder de combinatie weegt. Op de zwaarte sorteer ik hem achteraf.
Vervolgens match ik de combinaties met een string om te bepalen met welke (zwaarste) combinatie de string matcht. Van zwaar naar licht. De volgorde van de woorden zelf in de combinatie doen er op dit moment niet toe en voor zover ik het kan voorzien in de toekomst ook niet.

[ Voor 3% gewijzigd door Donderpoes op 29-07-2014 10:33 ]

[_Moe_]

Donderpoes schreef op dinsdag 29 juli 2014 @ 10:32:
Bedankt mensen. Ik heb mijzelf ingelezen en ik snap het nu

Een handig stukje wat ik ook ben tegen gekomen: http://r.je/php-find-every-combination.html


[...]


Mijn restrictie is dat de combinaties uniek moeten zijn uit de termen die de combinatie bevatten. Als ik 123 heb dan wil ik niet 231 hebben.
Aan elke combinatie hang ik een gewicht. Hoe meer woorden in een combinatie hoe zwaarder de combinatie weegt. Op de zwaarte sorteer ik hem achteraf.
Vervolgens match ik de combinaties met een string om te bepalen met welke (zwaarste) combinatie de string matcht. Van zwaar naar licht. De volgorde van de woorden zelf in de combinatie doen er op dit moment niet toe en voor zover ik het kan voorzien in de toekomst ook niet.

Misschien nog een stukje code?

[Donderpoes]

_Moe_ schreef op dinsdag 29 juli 2014 @ 10:42:
[...]


Misschien nog een stukje code?

Ben er nog mee bezig

[Soultaker]

Donderpoes schreef op dinsdag 29 juli 2014 @ 10:32:
Een handig stukje wat ik ook ben tegen gekomen: http://r.je/php-find-every-combination.html

Dit is wat minder geschikt als je kleine combinaties uit een grote set wil maken (bijvoorbeeld drie elementen uit een set van dertig).

[Vaan Banaan]

-Edit- Niet goed gelezen.

[ Voor 133% gewijzigd door Vaan Banaan op 29-07-2014 15:52 ]