[PHP] Recursief lettermogelijkheden.

[Verwijderd]

Oké, ik weet al wel dat ik recursiviteit moet gebruiken voor dit probleem.

Ik wil dus als je bvb ABC hebt dat hij daarvan alle mogelijke lettercombinaties geeft:
ABC, ACB, BAC, BCA, CAB, CBA

Hetzelfde bij bijvoorbeeld DEUR:
DEUR, DERU, DUER, DURE, DREU, DRUE, EDUR, ...

Ik zit nu bij een klein probleem...
Stel je hebt een 8 letterwoord, dan krijg je zeer grote arrays waardoor de server gewoon crasht.

Hoe los ik dit dan op?
Ook lukt het me niet om de recursieve functie op te bouwen.

[DRaakje]

Tjah, dat word moeilijk aangezien je gewoon geheugen te kort komt.
Het aantal mogelijkheden is namelijk (Lengte word)^26.
Maar waarom wil je dit doen?

[MadMurdock]

De recursieve functie zal eruit zien als:
- neem telkens de volgende letter van het woord
- sorteer de rest mbv deze functie..

Wat betreft je 8-letterwoord zie ik het probleem niet helemaal.. Misschien komt dat door je huidige functie.. Wat heb je nu dan?

edit:
Ahja, dit gebeuren heet dus permuteren, zoek daar eens verder op

[ Voor 13% gewijzigd door MadMurdock op 24-01-2005 16:22 ]

[Sendy]

Niet een array gebruiken maar die dingen meteen uitvoeren/afhandelen. Waarom moet het recursief?

Je weet wel dat al je een n letter woord gebruikt dat het helemaal lang duurt?

DRaakje >
Het is niet (lengte woord) ^ 26. Stel dat n de lengte van het woord is met m unieke letters. Het antwoord is dat (n!/((n-m)!*m!) (als mijn hersens me niet in de steek laten.)

8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 40320. Nog te bevatten; en zeker in een array te stoppen. Pas bij 13! a 14! worden en de mogelijkheden erg groot.

[ Voor 50% gewijzigd door Sendy op 24-01-2005 16:26 ]

[Verwijderd]

MadMurdock schreef op maandag 24 januari 2005 @ 16:19:
De recursieve functie zal eruit zien als:
- neem telkens de volgende letter van het woord
- sorteer de rest mbv deze functie..

Wat betreft je 8-letterwoord zie ik het probleem niet helemaal.. Misschien komt dat door je huidige functie.. Wat heb je nu dan?

edit:
Ahja, dit gebeuren heet dus permuteren, zoek daar eens verder op

Dat komt inderdaad door de arrays...

Maar zonder arrays lukt mij het gewoon niet...

[Janoz]

Wat moet er gebeuren met de gegenereerde woorden? Als je ze onthouden moet dan kom je niet om arrays heen. Hoef je het enkel uit te voeren dan kun je het natuurlijk ook direct afdrukken.

[BCC]

Ik denk dat je eerder een fout in je recursieve functie hebt zitten, want 8! is niet echt veel.

[lordsnow]

Leg eens uit wat je probeert te doen met een array vol met alle mogelijke lettercombinaties?
Als je dat eenmaal hebt... dan wat? Wat doe je met de array?

[Verwijderd]

Ik wil het "zonder" array, geen array dus maar direct afdrukken.
Daarmee kan ik raadsels gaan maken zoals op VT4 en VTM. :-D

In een array zetten kan ik later nog met "output buffering".

Maar de recursieve functie lukt mij niet.

[megamuch]

Verwijderd schreef op maandag 24 januari 2005 @ 16:50:
Ik wil het "zonder" array, geen array dus maar direct afdrukken.
Daarmee kan ik raadsels gaan maken zoals op VT4 en VTM. :-D

In een array zetten kan ik later nog met "output buffering".

Maar de recursieve functie lukt mij niet.

Voor de tiende keer, laat is wat zien.. Wat heb je al geschreven... Zonder die info kunnen we niets.

[BCC]

Da's toch niet zo moeilijk?
Pseudocode:

code:

functie blaat(x: string)
{
output="";

for (int i=0; i<length(x);i++)
{
    output .= x[i].blaat(x/[i]).",";
}

return output;
}

[ Voor 16% gewijzigd door BCC op 24-01-2005 16:55 ]

[Verwijderd]

megamuch schreef op maandag 24 januari 2005 @ 16:53:
[...]


Voor de tiende keer, laat is wat zien.. Wat heb je al geschreven... Zonder die info kunnen we niets.

Ik had het bestand verwijderd omdat het mijn server liet crashen dus ik heb momenteel niets meer.

Leg me gewoon even snel uit hoe ik die recursieve functie in elkaar moet steken want ik zit met het probleem dat hij bvb bij ABC AAB geeft ofzo en dat is niet de bedoeling, maar ik heb momenteel dus niets meer.

[Grijze Vos]

In pseudo code:

Neem een lijst met de letters, zeg {A,B,C}
Pak eentje eruit (A) en doe daarop dezelfde functie toepassen
zo ook voor B en C.

G({A,B,C})
=
A+G({B,C})

+
B+G({A,C})
+
C+G({A,B})

Beetje brak geformuleerd, but you get the idea.

[ Voor 5% gewijzigd door Grijze Vos op 24-01-2005 16:59 ]

[jvdmeer]

Je hoeft deze functie niet recursief te maken. Je kan 'm ook iteratief maken zonder een array te gebruiken.

code:

n=aantal letters
  verhoog teller van 0 tot n!-1
  begin met een string van n tekens bv sterretjes
    verhoog teller2 van 1 tot n
    plaats de (teller2)e op sterretje (teller mod (teller2-1)!)+1
  Druk de string af
eindig programma

Dus bij ABCD is het resultaat van de 1e keer binnenste lus:

code:

A***
AB**
ABC*
ABCD

2e keer

code:

A***
AB**
AB*C
ABDC

2e keer

code:

A***
A*B*
ACB*
ACBD

enz...

Geen probleem met geheugen dus ook niet bij n=20. Hooguit een probleem met rekentijd

PS: Zit even op mijn werk, dus kan het niet nader uitwerken naar een voorbeld. Zal indien nodig vanavond toelichten.

[ Voor 9% gewijzigd door jvdmeer op 24-01-2005 17:05 . Reden: PS toegevoegd ]

[Verwijderd]

Ik ga eens wat proberen te prutsen, lukt het niet...
Dan verwachten jullie een reactie deze week.

Laat het topic open a.u.b.

[Verwijderd]

Het is me gelukt dankzij jullie hulp en Zend Development Studio, zonder dat allemaal zou het me nooit gelukt zijn. De arrays zijn nuttig gebruikt, en dan krijg je resultaat.

Enige suggesties over het nog beter maken van het script zijn altijd welkom.

Wat vinden jullie ervan?

PHP:

<?
  // Variabelen intialiseren
  if (!isset($_GET['w'])) $woord = 'Woord';
  else  $woord = $_GET['w'];                // Woord
  $letters = array();       // Letters (Voor eertste While)
    
  // Alle letters voor de eerste loop ophalen (Sleutel ook letter geven voor handig verwijderen)
  for ($letter_i = 0; $letter_i <= (strlen($woord) - 1); $letter_i++) { $letters[$woord{$letter_i} . $letter_i] = $woord{$letter_i}; }
  
  // Output buffering
  ob_start();
    combi($letters, '');
        $contents = ob_get_contents();
    ob_end_clean();
    echo uniek ('<br>', verwijderlaatst($contents, 4));

    // Laatste karakters verwijderen
    function verwijderlaatst ($contents, $aantal) {
        return substr($contents,0,strlen($contents) - $aantal);
    }
    
    // Uniek maken
    function uniek ($seperator, $contents) {
        $contents = explode ($seperator, $contents);
        $contents = array_unique ($contents);
        return implode ($seperator , $contents);
    }
    
    // Recursieve combinaties functie
    function combi ($letters, $woord) {
        if (count ($letters) == 0) echo $woord . '<br>';
        else {
            foreach ($letters as $key => $letter) {
                $letters_combi = $letters;
                unset ($letters_combi[$key]);
                combi ($letters_combi, $woord . $letter);
            }
        }
    }
?>

EDIT: Paar overbodige dingen verwijderd en begin loop weggehaald.

[ Voor 21% gewijzigd door Verwijderd op 24-01-2005 18:33 ]

[dusty]

Verwijderd schreef op maandag 24 januari 2005 @ 18:16:
[..]
Wat vinden jullie ervan?
[..]

Ranzig.

Je gaat eerst elke letter eruit halen die als eerste eruit kan komen, en dan in een functie doe je dat ook weer. ( dus in je code staat in principe dubbele code. ), Er staat ook veel code in die niet nodig is voor je uitkomst. De oplossing kan namelijk een stuk korter.

[Verwijderd]

dusty schreef op maandag 24 januari 2005 @ 18:29:
[...]

Ranzig.

Je gaat eerst elke letter eruit halen die als eerste eruit kan komen, en dan in een functie doe je dat ook weer. ( dus in je code staat in principe dubbele code. ), Er staat ook veel code in die niet nodig is voor je uitkomst. De oplossing kan namelijk een stuk korter.

Al gewijzigd :-P

[dusty]

Verwijderd schreef op maandag 24 januari 2005 @ 18:33:
[...]
Al gewijzigd :-P

Ik herhaal:

Ranzig.

Je gaat eerst elke letter eruit halen die als eerste eruit kan komen, en dan in een functie doe je dat ook weer. ( dus in je code staat in principe dubbele code. )

[Verwijderd]

dusty schreef op maandag 24 januari 2005 @ 18:35:
[...]

Ik herhaal:

[...]

Hoezo? Nu is het toch niet meer dubbel,
ik wou gewoon even tonen wat ik al had tot nu toe.

Overigens, zie je nog iets wat sneller kan... Weg mag?

[dusty]

Verwijderd schreef op maandag 24 januari 2005 @ 18:16:
[..]

PHP:

for ($letter_i = 0; $letter_i <= (strlen($woord) - 1); $letter_i++) { $letters[$woord{$letter_i} .

...

PHP:

foreach ($letters as $key => $letter) {

Lijn 8 en 33.

Wat doe je bij beiden?

[Verwijderd]

Hoe wil jij dat korter maken?

Je moet de letters wel in een array krijgen hé.