All Possible Combinations of Letters

[Joe34]

Let's say I have the letters...

A,D, and G

And O (It's special)

How can PHP make all possible combinations with these words by using all or as little amount of letters as possible? (But special letters must be included in each scramble)

For example PHP would go through those letters and get...

A-O
O-A
O-D-G
D-O-G
G-D-O
D-G-O
A-D-G-O

And on and on and on...

What would be the fastest way to do this and if it is a function return those in an array?

[pritaeas]

Show the code you have already.

I would prebuild the intial arrays containing OA, OD, OG, OAD, OAG, ODG and OADG. For each of these, call a recursive function to display the possible results (or write it so it keeps looping, to avoid memory issues).

[pzuurveen]

I argee, a recursive function
but to get them all start with just O
than ad A, D or G before OR after
send each result through the same function

BIG problem: you need a stop condition or it will run indefinitely

[cereal]

stop condition is lenght: 4^1 + 4^2 + 4^3 + 4^4 = 340 possible combinations (or 336 if starting from 4^2)
when the script collects 340 unique combinations then it can stop.

[Joe34]

Anyone have a good idea on how this function will work? I'm having a hard time starting with this...

1. How can I make these combinations in the shortest amount of time?

2. Also would making all of the combinations be the best way to see if any of the combo's match with over 20,000 words in an array?

3. One more thing, it will actually have 7 seven letters (instead of four) (and each letter can only be used one per combo), but the number of letters that must be included will change...

Example:
7 Letters {R,A,R,H,S,L,L}
Special Letters {O,A,D}
* Note: Multiple special letters cannot come in the same combination, therefore combos will be 8 characters or shorter.
* Note: One letter will not be a combo Minimum: 2 Characters

[diafol]

is this homework?

[Joe34]

is this homework?

Nope, I'm working on a cool (complex) app!

[pritaeas]

If you have 7 and 3, then you'll have a lot more than 20.000 words ;)

Before we start, why don't you describe in text (pseudo code) how this should work.

[Joe34]

Here is how it should work...

Information:
- 20,000+ words stored in php array & MySQL table
- $_POST['yourletters'] seven letters player has in scrabble
- $_POST['boardletters'] 1 or more letters that have are available for use on board

Goal:
- Create legit words that contain letters from the $_POST['yourletters'] variable. The word must contain 1 letter from $_POST['boardletters'] (unless no board letters are given)

This is basically a Scrabble (The Game) cheat service.

[pritaeas]

Not what I mean.

Write down in text the steps you would take, if you had to do this by hand. For example:

Sort the letters
For each letter
  Combine with the fixed letter to make a two letter word

[Joe34]

That is the problem. I'm having a hard time figuring out this algorithm...

[diafol]

It's a nasty one and an intensive one. I've been trying to figure this one out, but I found a partial js solution here:

http://scriptar.com/JavaScript/permute.html

The basis is a fixed length permutator (non-repetitive element) and is QUICK.
I've tried to port it to php, with limited success. Will have another look.

[Joe34]

It's a nasty one and an intensive one. I've been trying to figure this one out, but I found a partial js solution here:

http://scriptar.com/JavaScript/permute.html

The basis is a fixed length permutator (non-repetitive element) and is QUICK. I've tried to port it to php, with limited success. Will have another look.

You rock dude! This is perfect!

Instead of doing the app in PHP I can echo the php array into a javascript array and go from there.

[cereal]

This may be helpful: http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm
bye :)

[diafol]

This may be helpful: http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm bye :)

That's even nicer for php! Nice one cereal.+1

Question - this is really intensive for the server - if a number of people are just tap, tap, tapping away - you could have a monster on your hands.
Using js, will place the load on the client. Just a thought.

[Joe34]

That's even nicer for php! Nice one cereal.+1

Question - this is really intensive for the server - if a number of people are just tap, tap, tapping away - you could have a monster on your hands. Using js, will place the load on the client. Just a thought.

That's what I was thinking too...

[Joe34]

Thanks everyone for your help, but I'm still having trouble implanting this into an algorithm.

I can't figure out how to do what I've said above.

[diafol]

I was looking at producing a set of combinations and then creating permutations on them. The possible number of combinations is huge in itself. Wondering too about creating a dummy letter (say X) for the mandatory letter and then using the js equivalent of array_map() - .map? replacing with O, A, D. Whether this would be quicker than creating each set of arrays?

Total number of permutations for 7 letters, 1 of three mandatories, decreasing in size from 8 to 2, *I think* will give: 328776 answers for all 3 mandatories.
Do you really need that much?

[Joe34]

Let me show you guys the overall task. I'm sort of building a Scrabble Cheating website.

The user provides two values
1. Their 7 Letters
2. 1 or more letters available on the board.

My job is to simply put that information together and use it to make real words they can place on the board.

What do I have?
1. An English MySQL dictionary (that can potentually be loaded into a javascript or php array)

My best guess was to start by making all of these permutations and be able to see if they matched with English words.

Any better ideas?

[diafol]

I suppose you could do this, but it seems very intensive to me. There again, I've never tried to do something like that before.

BTW - I'm still messing with some JS solution. I've got it to the point of producing combos and then running permutations on those. However, it won't deal with duplicate letters. Nowhere near finished. My pet project for the week! By then, I reckon somebody else will have a neat solution. Why not ask a mod to move this to the JS forum? That's where all the JS experts live.