[PHP] Woorden uit gegeven letters vinden

[jverdeyen]

Hoi,

ik heb mijn vraag reeds gesteld op heb webdev forum, maar hier werd gezegd dat dit een betere plek was om ze te stellen.

Nu,
mijn "webapplicatie" werkt als volgt:
- Een database vol 6 letter woorden
- Een form waar je 6 letters (max. 2x dezelfde) in kan geven.
-> Er wordt gezocht naar alle woorden die deze letter bevatten en geen andere.
Dit verloopt perfect.
Maar nu zijn er natuurlijk ook woorden die sommige letters meer dan 1x gebruiken, terwijl het maar 1x mag. Een voorbeeldje om duidelijk te maken
Ik geef volgende letters in:
L K O M P S
Volgende woorden zijn dan valide:
LOMP, SOP, KOP, ... enz
Volgende woorden zijn niet valide:
LOOK, POOS, LOOS, .. enz

Hoe kan ik deze het best hieruit 'filteren'.
Hoe kan ik bepalen dat een woord 'teveel' letters gebruikt dan dat er zijn.
Ik heb al veel dingen geprobeerd zoals letters disablen als ze gerbruikt zijn in een woord etc..

Alvast bedankt!

[TheRookie]

jverdeyen schreef op woensdag 26 juli 2006 @ 12:54:

Ik heb al veel dingen geprobeerd zoals letters disablen als ze gerbruikt zijn in een woord etc..

Wat lukte hier niet aan, dit lijkt me namelijk de meest voor de hand liggende oplossing ?

[ Voor 4% gewijzigd door TheRookie op 26-07-2006 12:59 ]

[NMe]

Wat is er mis met Janoz' oplossing in je andere topic?

[jverdeyen]

Even snel mijn werkwijze uitleggen

totaal=0

for (overloop de array van woorden){
- zet de gegeven letters in een temp array (om bij elk woord opnieuw te vullen)
for(overloop elke letter van het woord){
for(overloop de gegeven letters){
if(is de letter van het woord == een letter van de gegeven letters & is deze nog beschikbaar){
maak de letter niet meer beschikbaar
tel 1tje bij totaal
}
}
if(totaal == lengte van het woord) {
druk het woord af want voor elke letter in het woord is er eentje in de gegeven letters
}

}


ergens klopt er iets niet in men werkwijze ...

[jverdeyen]

-NMe- schreef op woensdag 26 juli 2006 @ 13:00:
Wat is er mis met Janoz' oplossing in je andere topic?

kreeg ik ook niet aan de praat

[NMe]

Je hebt het over een database in je startpost, maar in je uitleg hier doorloop je ineens een array. Je kan dit grotendeels/helemaal in je database oplossen, PHP heb je niet nodig bij die oplossing van Janoz. Wat lukte daar precies niet aan?

[MicroWhale]

wat is er dan mis met je eigengemaakte oplossing hierboven?

[jverdeyen]

-NMe- schreef op woensdag 26 juli 2006 @ 13:07:
Je hebt het over een database in je startpost, maar in je uitleg hier doorloop je ineens een array. Je kan dit grotendeels/helemaal in je database oplossen, PHP heb je niet nodig bij die oplossing van Janoz. Wat lukte daar precies niet aan?

In mijn database roep ik alle woorden op die deze letters gebruiken, maar kan ik dan ook bepalen hoeveel keer deze mogen voorkomen ? Dan moet ik idd alleen mijn query aanpassen.
En deze resultaten steek ik in een array van woorden ...

[GlowMouse]

Met count_chars, een foreach loop en een enkele if-constructie is dit vrij eenvoudig te doen.

[Tjark]

misschien een idee: maak van alle woorden in je database een vector:

code:

         ABCDEFGHIJKLMNOPQRSTUVWXYZ
LOMP     00000000000110110000000000
BAR      11000000000000000100000000
FOO      00000100000000200000000000

dan is
LKOMPS   00000000001110110010000000

zoek dan in de database

where vector like '0000000000[01][01][01]0[01][01]00[01]0000000' and vector like '%1%'

probleem is wel dat je nog zooi in je database hebt staan die '2' ... '6' kunnen bevatten blijkbaar, maar als je die toch niet wil, waarom zitten ze in je databeest?

(of toevoegen aan de query: and vector not like '%[23456]%' )

groot voordeel: 1x wat in de database zetten, en al dat geloop-werk zit dan mooi in de DB query.

[ Voor 214% gewijzigd door Tjark op 26-07-2006 13:21 ]

[jverdeyen]

GlowMouse schreef op woensdag 26 juli 2006 @ 13:09:
Met count_chars, een foreach loop en een enkele if-constructie is dit vrij eenvoudig te doen.

owh idd, en met substr_count lijkt dit ook wel mogelijk.
Ik ga het straks eens probernen alvast bedankt!!!

[NMe]

TjarkVerhoeven schreef op woensdag 26 juli 2006 @ 13:13:
misschien een idee: maak van alle woorden in je database een vector:

code:

         ABCDEFGHIJKLMNOPQRSTUVWXYZ
LOMP     00000000000110110000000000
BAR      11000000000000000100000000
FOO      00000100000000200000000000

dan is
LKOMPS   00000000001110110010000000

zoek dan in de database

where vector like '----------111-11--1-------'

probleem is wel dat je nog zooi in je database hebt staan die '2' ... '6' kunnen bevatten blijkbaar, maar als je die toch niet wil, waarom zitten ze in je databeest?

(of toevoegen aan de query: and vector not like '%[23456]%' )

Maak dan asjeblieft gewoon een tabel met een veld voor elke letter van het alfabet, maar daarin een frequentie van hoe vaak die letter in dat woord voorkomt.

letter_frequentie
id, woord_id, a, b, c, ..., y, z

"Lomp" heeft dan bijvoorbeeld het id 1 in de woordentabel, en heeft alle letters op 0 staan, afgezien van de L, de O, de M en de P, waar een 1 staat. Voor "poos" geldt dat ook; woord_id 2, alles op 0, afgezien van de P en de S, die op 1 staan, en de O, die op 2 staat.

Je hoeft dan vooraf alleen maar te bepalen welke letters je hebt, en hoeveel daarvan er zijn. Vervolgens hoef je alleen maar die woorden op te halen waarin een letterfrequentie kleiner of gelijk is aan het aantal van die letter dat je tot je beschikking hebt.

Om een en ander wat sneller te laten verlopen kun je eerst eens alle woorden opzoeken die geen letters gebruiken die je niet mag gebruiken, door middel van een regexp, wat ook binnen bijvoorbeeld MySQL kan.

[GlowMouse]

jverdeyen schreef op woensdag 26 juli 2006 @ 13:13:
[...]
owh idd, en met substr_count lijkt dit ook wel mogelijk.
Ik ga het straks eens probernen alvast bedankt!!!

Na count_chars heb je substr_count niet meer nodig
Maar ik zie alleen nu dat het probleem is dat je ze in een database hebt staan. Afhankelijk van het aantal database-entries is het doorlopen van elk woord niet bevorderlijk voor de performance. Helaas heeft (in ieder geval MySQL) geen functie als substr_count, dus dan wordt het een stukje lastiger om dit in 1x met een query te doen. Ik zou geneigd zijn een extra tabel toe te voegen met daarin de velden woord_id,char,count.

[Tjark]

-NMe- schreef op woensdag 26 juli 2006 @ 13:19:
[...]

Maak dan asjeblieft gewoon een tabel met een veld voor elke letter van het alfabet, maar daarin een frequentie van hoe vaak die letter in dat woord voorkomt.

letter_frequentie
id, woord_id, a, b, c, ..., y, z

"Lomp" heeft dan bijvoorbeeld het id 1 in de woordentabel, en heeft alle letters op 0 staan, afgezien van de L, de O, de M en de P, waar een 1 staat. Voor "poos" geldt dat ook; woord_id 2, alles op 0, afgezien van de P en de S, die op 1 staan, en de O, die op 2 staat.

Je hoeft dan vooraf alleen maar te bepalen welke letters je hebt, en hoeveel daarvan er zijn. Vervolgens hoef je alleen maar die woorden op te halen waarin een letterfrequentie kleiner of gelijk is aan het aantal van die letter dat je tot je beschikking hebt.

Om een en ander wat sneller te laten verlopen kun je eerst eens alle woorden opzoeken die geen letters gebruiken die je niet mag gebruiken, door middel van een regexp, wat ook binnen bijvoorbeeld MySQL kan.

with stupid!

kan ook, maar levert weer zoveel kolommen op

[ Voor 4% gewijzigd door Tjark op 26-07-2006 13:24 ]

[NMe]

...wat een stuk makkelijker werkt en sneller is dan zo'n vectorstring. Om nog maar niet te spreken over woorden die meer dan 9 keer dezelfde letter bevatten.

[Tjark]

gelukkig is de db maar 6 letterig
maar zeker true true!

[jverdeyen]

ok bedankt iedereen.
Vanavond ga ik dat eens uittesten.
k had het wat onderschat.