[php] nummerpermutaties vinden

[Verwijderd]

Ik wil van een serie getallen alle mogelijke combinaties hebben, waarbij een enkel getal niet herhaald wordt in één combinatie.
Kortom: "Permutaties n uit n", want de combinaties moeten alle gegeven getallen bevatten.

Ik ben al eventjes aan het zoeken geslagen en het áántal verschillende combinaties kan gevonden worden door de faculteit van n te nemen: n! (d.w.z., faculteit 3 = 3*2*1 = 6).

Een ding kom ik echter niet uit, ondanks het feit dat Soultaker hier een oplossing aandraagt (maar jammer genoeg geen complete want als als eerste argument ($left) het aantal array-elementen in de eerste instantie wordt meegegeven dan werkt de functie niet - oftewel, als in zijn voorbeeld i.p.v. een 3 een 4 wordt gegeven doet de functie niet meer wat hij moet doen).

Voor de duidelijkheid de hamvraag;
Hoe kan ik - praktisch - met behulp van PHP alle mogelijke combinaties van een serie getallen terugkrijgen, zonder getallen meerdere malen te tonen in één combinatie? Ik neem aan met recursiviteit, maar concreet kan ik de oplossing niet vinden dus ik moet mij beroepen op meer wiskundig aangelegde mensen dan ik..

_{Voor de duidelijkheid een voorbeeld van input/output:}

Input:

code:

array(1,2,3);

output:

code:

array(
0 => 1,2,3
1 => 1,3,2
2 => 2,1,3
3 => 2,3,1
4 => 3,1,2
5 => 3,2,1
);

[masser120]

Om het nog ingewikkelder te maken (en bijna compleet onoplosbaar ):

"geeneen" bevat 4x een "e" en 2x een "n". Totaal zijn het 7 letters. Als je dan normaal gaat permuteren krijg je meerdere keren dezelfde combinatie te zien. Daarom moet je de formule veranderen. Je moet het totale aantal letters (n!) delen door de letters dubbel in de factor tijd.
Dus:
(7!)/(4!*2!) = 105

"natuurkundeleraar" bevat 3x a, 3x u, 2x n, 2x r, 2x e, 2x r en totaal 17 letters.
Dus:
(17!)/(3!*3!*2!*2!*2!*2!) = 617 512 896 000 (niet slim om zo iets in te voeren )

Enzovoort...

[ Voor 23% gewijzigd door masser120 op 15-02-2006 20:09 ]

[Verwijderd]

Een dubbel(e) letter/getal komt in mijn situatie niet voor gelukkig.

[-Tibo-]

*getallen* ?

[BCC]

Dit is wel erg basis recursie. Pseudo code:

code:

Functie Premute(array input[])
  returnArray[];
  for (int i=0 i< input.length(); i++) {
    //Sloop het geselecteerde element uit de array
    tempArray = inputArray - input[i] element

     //Ga hiermee verder
     returnArray.add (input[i] + Premute(tempArray);
  }
 
return returnArray

Je moet even iets intelligenters doen met de return arrays of het als een boom opslaan (ook leuk).

En voor 't tweede stuk, dat is een eitje als je het eerste hebt. Filter gewoon alle dubbele letters eruit en doe hetzelfde als in je eerste vraag. Permute(geeneen) -> Permute(gen)

[ Voor 32% gewijzigd door BCC op 15-02-2006 20:38 ]

[Varienaja]

Verwijderd schreef op woensdag 15 februari 2006 @ 19:48:
Ik wil van een serie getallen alle mogelijke combinaties hebben, waarbij een enkel getal niet herhaald wordt in één combinatie.

Het bedenken van algoritmen is de basis van het programmeren natuurlijk. Dat moet je gewoonweg in de vingers gaan krijgen, anders knutsel je nooit wat leuks in elkaar. Stap 1 daarbij is om op te schrijven wat je wilt bereiken. Dat heb je al prima gedaan: blijkbaar kan je in je hoofd het algoritme al uitvoeren. Het enige wat je dan nog moet doen is het algoritme in computertaal opstellen. Dat vergt flinke oefening. Hierbij een hint:

code:

procedure Perms(Array a,b; index i)
   if (i=sizeof(a)) doe iets met array b;

   for t:=i to sizeof(a)
      neem a[t] als i-de element in array b
      Perms(a,b,i+1)
   end;
end

Huiswerkvraag: vind de faculteit hierin terug.

Eigenlijk heb ik 't nu al compleet voorgezegd...

[Verwijderd]

Dit gaat erg NOOB-istisch overkomen; heb inmiddels het volgende.

PHP:

function Perms($array_a, $array_b, $i) {

    if($i=sizeof($array_a)) {
        echo $array_b.'<br>';
    }

    for($t=$i;$t<sizeof($array_a);$t++) {
        Perms($array_a,$array_b, $t);
    }

}

Waarbij ik uiterst goed besef dat dit verre van goed is. Het is wel gebaseerd op de pseudocode van Varienaja, maar ik kom er ondanks die grote hint níet uit.
Zoals Varienaja zelf al zegt, ik snap precies wat er moet gebeuren in mijn hoofd maar het komt er simpelweg niet uit in de taal waar ik mee werk momenteel, PHP. Zou bijzonder fijn zijn als iemand de laatste schop onder mijn zitvlak geeft wat deze code betreft, daar het een belangrijk onderdeel is van een veel groter projectje.

[Soultaker]

Ik moet toch even mijn code verdedigen hoor.

Verwijderd schreef op woensdag 15 februari 2006 @ 19:48:
Een ding kom ik echter niet uit, ondanks het feit dat Soultaker hier een oplossing aandraagt (maar jammer genoeg geen complete want als als eerste argument ($left) het aantal array-elementen in de eerste instantie wordt meegegeven dan werkt de functie niet - oftewel, als in zijn voorbeeld i.p.v. een 3 een 4 wordt gegeven doet de functie niet meer wat hij moet doen).

Hij doet wél wat hij moet doen, maar de titel van het topic dat je aanhaalt is niet voor niets "alle mogelijke combinaties van array weergeven". Als je uit een array met vier elementen alle combinaties van vier lang wil weergeven, dan krijg je dus inderdaad maar één resultaat omdat in een combinatie de volgorde van de gekozen elementen niet uitmaakt (dat is ook het essentiële verschil tussen een combinatie en een permutatie).

Voor het genereren van permutaties zijn meerdere mogenlijkheden. Als je simpelweg alle permutaties wil vinden kun je recursie gebruiken; in pseudo-code:

code:

Perm(Array a)
  Voor elk element x in a:
    Voor elk element b in Perm(a zonder x):
        x:b is een nieuwe permutatie

Ik moet trouwens bekennen dat ik Varienaja's pseudo-code ook niet begrijp. Het lijkt me dat als je 'm werkend wil krijgen, je het uit array a gekozen element er echt uit moet halen (en dus niet recursief doorgeven) anders kan een enkel element meer dan eens voorkomen. Als je 'm uit a haalt werkt de sizeof()-controle natuurlijk niet meer. Ik zou Varienaja's code zo willen herschrijven:

code:

Perm(Array a, Array b)
  Als a leeg is:
    b is een permutatie
  Voor elk element x uit a:
    Perm(a zonder x, b:x)

In principe komt het op hetzelfde neer als mijn code, maar de implementatie is wat anders (ik geef de tussenresultaten terug als return values, Varienaja geeft de tussenresultaten mee als argumenten aan de functies). Overigens heeft Varienaja gelijk dat het belangrijk is om eerst te begrijpen hoe dit soort algoritmen werken, voordat je je over de implementatie druk gaat maken.

Er zijn verder ook technieken om een bestaande permutatie in een volgende om te zetten, zo, dat ze allemaal voorbijkomen. Je hebt dan dus een functie F die de 'volgende' permutatie geeft voor een array a. Als je die functie sizeof(a) ! (lengte van a, faculteit) keer toepast op a, dan heb je je oorspronkelijke a weer terug. Als je wil kan ik daar morgen wel op in gaan.

[ Voor 11% gewijzigd door Soultaker op 15-02-2006 23:42 ]

[Varienaja]

Soultaker schreef op woensdag 15 februari 2006 @ 23:39:
Ik moet trouwens bekennen dat ik Varienaja's pseudo-code ook niet begrijp.

Dat zou kunnen, volgens mij klopt het namelijk ook niet 100%. 't Is altijd lastig om code te schrijven zonder er een compiler naast te hebben.

Ik heb hier een stukje Java, waarvan ik wel zeker ben dat 't werkt:

code:

    /**
     * Genereert alle volgordes van stukjes (6! == 720)
     * @param stukjes
     * @param d
     * @throws Exception 
     */
    private void pak(List<Integer> stukjes, int d) throws Exception {
        Iterator<Integer> i = stukjes.iterator();
        
        while (i.hasNext()) {
            List<Integer> tmpList = new LinkedList<Integer>(); 
            tmpList.addAll(stukjes);
            
            Integer stukje = i.next();
            _config[d] = stukje;
            
            tmpList.remove(stukje);
            
            if (tmpList.size()>0) {
                pak(tmpList,d+1);
            } else { //Er is een volledig gevuld spel: draaien!
                draai(0);
            }
        }
    }

[Verwijderd]

Hartelijk dank beide, ik weet zeker dat ik hier wat mee kan en dat ik uiteindelijk ga snappen wat de functie doet (want dát wil ik leren, wat er gebeurd in de functie - niet wat het resultaat is).
Korte vraag waar ik misschien vanzelf achterkom als ik de functie ga ontleden; wat zijn de waarden waar de functie Perm() in het tweede stukje psuedocode van Soultaker mee aangeroepen moet worden in de eerste instantie, dus de eerste en niet-recursieve call?

_{Zal binnenkort even het resultaat posten}

[Soultaker]

Argument a is de resterende invoer (die nog ingevoegd moet worden in de permutatie) en b is de permutatie 'tot nu toe'. Bij de eerste aanroep is a dus de volledige array en b een lege array.

Het algoritme werkt dan ook door bij elke recursieve aanroep een element van a naar b over te hevelen. De som van het aantal elementen in a en b is dus altijd hetzelfde (gelijk aan het totale aantal elementen in de oorspronkelijke array) - als a leeg is en b (dus) vol, is b een permutatie van de oorspronkelijke array.

[Verwijderd]

Soultaker schreef op donderdag 16 februari 2006 @ 16:17:
Argument a is de resterende invoer (die nog ingevoegd moet worden in de permutatie) en b is de permutatie 'tot nu toe'. Bij de eerste aanroep is a dus de volledige array en b een lege array.

Het algoritme werkt dan ook door bij elke recursieve aanroep een element van a naar b over te hevelen. De som van het aantal elementen in a en b is dus altijd hetzelfde (gelijk aan het totale aantal elementen in de oorspronkelijke array) - als a leeg is en b (dus) vol, is b een permutatie van de oorspronkelijke array.

Bovenstaand gaf de doorslag, de oplossing die ik gevonden heb is er een geworden waarbij gebruik wordt gemaakt van string i.p.v. arrays. Voor de liefhebber:

PHP:

// Let op; bij input strings met een lengte van 7+ wordt
// de executiontime erg hoog (zoniet onacceptabel).
// Dit wordt veroorzaakt door de faculteit van de lengte.
// Zie: http://nl.wikipedia.org/wiki/Faculteit_%28wiskunde%29
function Perm($string_a, $string_b) {

    if(!isset($result)) $result = array();
    static $result;
    
    if(strlen($string_a) == 0) {
        $result[] = $string_b;
    } else {        
        for($pos=0;$pos<strlen($string_a);$pos++) {
            $char = substr($string_a,$pos,1);
            Perm(
                str_replace($char,"",$string_a),
                $string_b.$char
            );
        }
    }

    return $result;
}

$permutations = Perm('abcd','');

// bovenstaande functie kan slechts eenmaal per 
// script aangeroepen worden i.v.m. de static $result
// variabele. Hier zijn echter prima work-arounds voor.

[ Voor 12% gewijzigd door Verwijderd op 17-02-2006 09:22 ]