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

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 seven letters player has in scrabble
- $_POST 1 or more letters that have are available for use on board

Goal:
- Create legit words that contain letters from the $_POST variable. The word must contain 1 letter from $_POST (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...

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 :)

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.

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?

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.

[Joe34]

Okay I moved the thread and now some JS experts are here to help!

[Airshow]

I think there's a problem with doing this in JS.

Whereas the load associated with generating combinations and permutations (combs and perms in mathematical jargon) would be delegated to the client, you would then end up with either:

• a nightmarishly large HTTP request
• a nightmarishly large number of small HTTP requests.

I would recommend keeping the algorithm server-side and employing an Anagram Dictionary approach thereby limiting the hard work to generating and testing a manageable number of combs, ie avoiding the need to generate and test a very large number of perms.

Airshow

[Joe34]

I think there's a problem with doing this in JS.

Whereas the load associated with generating combinations and permutations (combs and perms in mathematical jargon) would be delegated to the client, you would then end up with either:

• a nightmarishly large HTTP request
• a nightmarishly large number of small HTTP requests.

I would recommend keeping the algorithm server-side and employing an Anagram Dictionary approach thereby limiting the hard work to generating and testing a manageable number of combs, ie avoiding the need to generate and test a very large number of perms.

Airshow

Thanks for the suggestion, but I still want to do it in JS. I don't care if the script takes one minute to do what I want it to do. Anyone that gives me some code that works will be highly thanked!

[Airshow]

If you really must, then you can work out the combs in JS and pass them server-side (ajax GET or POST request).

Under no circumstances work out all the perms either client-side or server-side. Use the Anagram Dictionary approach.

There's quite a lot of work ahead of you. There's way too much for anyone to write it for you (except on a commercial basis) but here's a plan of action:

1. Find an open source Anagram Dictionary or convert your current dictionary to the Anagram Dictionary format. I have never done this but the Wikipedia link (above) should give some clues where to start; if not, then Google.
2. Write a PHP script to receive a $_GET or $_POST array of character combinations, enquire the Anagram Dictionary and echo the matching words, json-encoded.
3. In javascript, write a function combs(optionalCharArray, mandatoryCharArray){...} , which returns an array or all legal character combinations (not permutations).
4. In javascript, write a master routine that calls combs(...), makes an ajax call to your PHP script, and handles the response to display the results on the page. This will be the glue that puts all the pieces together.

Airshow

[cereal]

Adding a piece to Airshow's puzzle: you can use Pspell library in PHP which uses a word list dictionary to match submitted words, this will be more fast than repeatedly querying the database, an example:

<?php
$w = 'door';
if($w != false)
{
    $pspell_link = pspell_new("en"); # set language
    if(pspell_check($pspell_link, strtolower($w))) {
	echo $w;
    }
}
?>

This library is not installed by default, so if you are in Debian/Ubuntu you can install it by typing sudo apt-get install php5-pspell in a shell. The library is part of the aspell project:

pspell: http://www.php.net/manual/en/book.pspell.php
aspell: http://aspell.net/

The dictionary is installed by the library but you can use whatever you want.
Apart from suggested solutions by Ardav and Airshow, I've tried to use Pspell with a script in the article I've posted above, and it works but I think it isn't still a usable solution, it's rough, bloody heavy on CPU and not complete, if you want to try:

<?php

function pc_permute($items, $perms = array( )) {
    if (empty($items)) {
        $w = join('', $perms);
	$pspell_link = pspell_new("en"); # set language

	if (pspell_check($pspell_link, strtolower($w))) {
		echo $w . "\n"; # just match submitted words
	}

	/* uncomment below to get suggestions
	else
	{
	    $suggestions = pspell_suggest($pspell_link, $w);
            foreach ($suggestions as $suggestion) {
                echo "Possible spelling: $suggestion \n";
            }
	}
        */

    }  else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
	     usleep(2000); # slow down for CPU
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems, $newperms); # recursive loop
         }
    }
}

$a = array('d','r','s','l'); # input
$b = array('o','a','e'); # input
$c = array_merge($a,$b);
pc_permute($c); # run

echo "\n";
?>

bye

[pritaeas]

C# example found on SO.