[PHP] Woordenlijst: $a + $b + $n = 50

[Verwijderd]

Beste allemaal, ik ben bezig met een tooltje om een string van precies x karakters te vullen met random woorden. Ik geef aan uit hoeveel woorden de string moet bestaan en wat de tussenkarakters zijn (en zo zijn er nog wat eisen). Vervolgens scant een scriptje in fase 1 een taalbestand op woorden die voldoen aan de eisen. In fase 2 worden die woorden en tussenkarakters (meestal komma gevolgd door spatie) op brute-force wijze net zo lang gecombineerd totdat een string van precies x karakters ontstaat. Al met al kan dat behoorlijk wat processortijd kosten.. volgens mij moet dat een stuk slimmer kunnen. Ik ben echter niet zo wiskundig aangelegd...

Is het mogelijk om een vergelijking als $a + $b + $c + $n = x chars op te lossen, waarbij $n tussen y en z ligt?

Bijvoorbeeld: y = 3, z = 5. Dan een vergelijking als $a + $b + $c + $d = 15 levert 3 + 5 + 4 + 3 = 15 op.

In dat geval selecteert het scriptje namelijk een wood van 3, 5, 4 en 3 characters om zo op de totale lengte van 15 uit te komen.

Zijn er andere manieren om dit probleem op te lossen? Overigens, voor fase 1 is op dit moment al een cachingmechanisme, fase 2 is in principe niet te cachen omdat er telkens een andere string teruggegeven moet worden.

[ Voor 4% gewijzigd door Verwijderd op 15-11-2005 11:10 ]

[wasigh]

Een vergelijking met 1 onbekende is toch erg makkelijk op te lossen?
als A,B,C bekend zijn dan is het toch simpel om D uit te rekenen met: D = 15 - A - B - C ?

Stel X is het aantal karakters.
Ik zou beginnen met scannen welke lengtes van woorden je allemaal hebt. Daarna ga je (wellicht random?) een A pakken met een lengte tussen 1 en X - 3.. dan bereken je hoeveel karakters je nog over hebt: X = X - lengte(a); en pak je een B met lengte tussen 1 en X - 2 etc.

Loop je op het einde vast omdat je bijvoorbeeld voor D een woord van 1 letter moet hebben maar je die niet hebt. Dan pak je een andere waarde voor C en probeer je het opnieuw.

Overigens zou ik de woorden vandezelfde lengte bij elkaar in Arrays zetten oid.

[T-MOB]

Je bent je er van bewust dat je vergelijking een aantal oplossingen heeft? 4+4+4+3 is ook 15, net als 5 + 5 + 2 + 3 en zo zijn er nog tig te bedenken. Wat me verder nog niet echt duidelijk is is of je 1 of meer combinaties terug wil hebben (of alle).

Om het proces te versnellen zou ik overigens de woordenlijst splitsen in sublijsten met woorden van gelijke lengte. Je kunt dat doen in fysiek verschillende lijsten, of door eenmalig te kijken bij welke entry woorden van x karakteres beginnen en eindigen in een lijst gesorteerd op lengte. Je kunt dan gewoon rand($begin, $eind) pakken voor een woord van bepaalde lengte.

[Zoijar]

Als ik het goed begrijp het je het over het "knapsack" probleem, of in ieder geval een redelijk rechtstreekse variant daarvan. Verbazingwekkend genoeg is dit probleem erg moeilijk (NPC). Het makkelijkste is om een search tree te gebruiken; ongeveer wat waisgh zegt. Begin gewoon met een woord dat kan, zoek er een tweede woord bij dat nog steeds kan, tot dat je vast loopt of een oplossing hebt. Als je vastloopt ga je een stapje terug en kies je een ander woord op dat moment.

[curry684]

Zoijar schreef op dinsdag 15 november 2005 @ 12:36:
Als ik het goed begrijp het je het over het "knapsack" probleem, of in ieder geval een redelijk rechtstreekse variant daarvan. Verbazingwekkend genoeg is dit probleem erg moeilijk (NPC). Het makkelijkste is om een search tree te gebruiken; ongeveer wat waisgh zegt. Begin gewoon met een woord dat kan, zoek er een tweede woord bij dat nog steeds kan, tot dat je vast loopt of een oplossing hebt. Als je vastloopt ga je een stapje terug en kies je een ander woord op dat moment.

Dat noemen we ook wel 'brute force'

Het is inderdaad het knapsack probleem overigens, en daar zijn best betere implementaties voor te bedenken dan bruteforcen. In dit geval zou je er bijvoorbeeld voor kunnen kiezen om de gemiddelde lengte van de beschikbare woorden te nemen en daarmee proberen uit te vullen. Daarmee voorkom je situaties waarin je 9 letters moet vullen, je een woord van 8 letters kiest om te beginnen en vervolgens voor nop door alle woorden loopt omdat je er toch geen van 1 in hebt staan.

[T-MOB]

Waarom zou je de woorden langslopen. Als de woordenlijst vast staat kun je toch volstaan met het oplossen van de vergelijking a+b+c+d=x (met a-d <j,k>). Je kunt dan toch voor a-d random getallen tussen j en k nemen, eventueel gecorrigeerd voor de verhoudingen waarin woorden van een bepaalde lengte voorkomen in je woordenlijst. Wanneer je een geldige uitkomst hebt hoef je pas woorden te selecteren.

[Verwijderd]

Ik denk dat het handig is als TS even aangeeft of meerdere (verschillende) combinaties mogen voorkomen in de resultaten. Zoals T-MOB aangeeft in een eerdere post.

[Grijze Vos]

Het is SUBSET-SUM, een speciale variant van knapsack.
(Joy, morgen tentamen complexiteit.)

Dit probleem is inderdaad NPC, maar als je sets voldoende klein zijn zou het niet al te lang hoeven duren.

[Zoijar]

curry684 schreef op dinsdag 15 november 2005 @ 12:53:
Dat noemen we ook wel 'brute force'

Het is inderdaad het knapsack probleem overigens, en daar zijn best betere implementaties voor te bedenken dan bruteforcen. In dit geval zou je er bijvoorbeeld voor kunnen kiezen om de gemiddelde lengte van de beschikbare woorden te nemen en daarmee proberen uit te vullen. Daarmee voorkom je situaties waarin je 9 letters moet vullen, je een woord van 8 letters kiest om te beginnen en vervolgens voor nop door alle woorden loopt omdat je er toch geen van 1 in hebt staan.

True. Maar dat is niet fundamenteel beter: dat zijn zoek optimalisaties. Elke keer dat je een keuze hebt in je zoekboom, kan je 'slim' kiezen om eerder tot een oplossing te komen. Maar in het slechtste geval hebben die slimme keuzes geen toegevoegde waarde. In de praktijk heb je natuurlijk gelijk, want het zal er gemiddeld (veel) sneller door draaien. Toevallig ben ik net met iets soortgelijks bezig (subgraaf isomorfismen), en het sorteren op graad van de vertices bij het kiezen helpt daar gigantisch. Theoretisch is het echter nog steeds een exponentieel algoritme.

Maw. al die betere/snellere complexe algoritmes voor dit soort problemen zijn gebasseerd op slimmer zoeken door sneller takken af te kappen, of als er slechts een oplossing is gewenst om eerder daar op uit te komen. Het onderliggende algoritme, en de worst-case, zijn altijd "brute-force".

[Zoijar]

Grijze Vos schreef op dinsdag 15 november 2005 @ 13:16:
Het is SUBSET-SUM, een speciale variant van knapsack.
(Joy, morgen tentamen complexiteit.)

Dit probleem is inderdaad NPC, maar als je sets voldoende klein zijn zou het niet al te lang hoeven duren.

Ik geloof je op je woord Het aantal oplossingen is met een gesloten vergelijking te bepalen toch? Sterling getallen is het niet? Er staat me iets bij... het houdt verband met het aantal factorisaties van polynomen dacht ik. (aangezien je dan groepjes factoren moet vormen waarvan de som van de exponenten gelijk aan de graad van het polynoom moet zijn) Ten slotte is het denk ik gerelateerd aan het aantal verschillende kwadratische vormen en projectieve curven (want direct gerelateerd aan polynoom factorisaties). Leuk toch hoe er zo veel verbanden in de wiskunde zijn tussen totaal verschillende toepassingen.