Programming Question - Combinations/Permutations

[Matt Vinyl]

Hi all, seeing as though I'm still off work (for another week and a half! ) I've actually made some headway in my word game I've been creating.

I've hit a bit of a problem, and I can't seem to work this out...

Let me set out the constraints / rules:

- A word is randomly selected from a dictionary that is 8 letters in length.
- The word that is selected must have at least 12 other words 'within' itself.
- A player must make as many words from this word as possible.
- The words made by the player can be from 3 to 8 letters in length.

Now, what I can't work out, is an algorithmn that would find all the possible words that can be made from the original 8 letter word. I'm not really asking for 'the code' that'd do this, but more conceptual ideas on how to go about it. So far, I've split the word up into the 8 individual letters, but that's it...

Any suggestions?

Cheers,
M.

[Matt Vinyl]

Ah, just now need to find out how many possible combinations of letters you can have within an 8 letter word. Anyone know? My statistics A-level was 8 years back, and I remember the phrases combinations / perumtations, but am not sure which one applies to this.

Obviously, if there are (for example) 2x 'a's within a word (such as "ARRANGED", I only want to include the possible word "ARE" once. As it could be made with both the first A and the second A (fourth letter).

I'll continue Googling, of course...

[Mattb]

Well for an 8 letter word there would be 40,320 different orders you could have the letters in. Now obviously those won't all be real words will they, so i've got no idea how you'd get it to work out what words could be made from a set!

[Cardinal Sin]

I don't know if it would be the most efficient way of doing it, but you could just use a series of nested loops surely? A pain in the arse to work out, but it would ensure you get all the permutations.

[Matt Vinyl]

Cheers, now the fact that they are not all real words isn't a problem, as all I then need to do is check each combination against each word in the dictionary to see if it is indeed a real word. This of course, will only check 8 letter words.

The next step is to see how many 3, 4, 5, 6 & 7 letter combinations there are and check those against the dictionary. (Not sure about this step!) Plus, how did you work out the combination number mate?

This all sounds involved, and I've got a dictionary of 117592 words, but it only takes 0.02 of a sec to load 'em all in and randomly find an 8 letter word, so speed won't be an option...

Cheers though, at least with that number I can make a start...

[Matt Vinyl]

Nested Loops - very true, I think it might be OK to use that in this situation, as there are a finite number of 'elements'...

Still a struggle though. Having looked around the web, there are programmes that people are selling that work it out for you, so it must take a bit of work to put it all together...

[admin]

Will have a little think about this for you..

Will be dead easy to check all the possible combinations against a dictionary, but might be a bit slugish.. If I suddenly habe a brain wave I will let you know.

Edit: Matt can you send me the dictionary?

[Matt Vinyl]

Cheers my man!

Yup, easy to check against the dictionary, but need to get the combinations first...

[admin]

Can you send me the dictionary?

[Matt Vinyl]

No probs, Mail it to you now. (PS - has the PM attachment problem sorted itself out?)

[Cardinal Sin]

The 40,320 is 8*7*6*5*4*3*2*1 or the number of different possible 8 letter words you can get out of 8 letters. This doesn't take into account the 3-7 letter words, which will be rather more complex to do (and a bit of a pain in the arse i'd imagine).

As for making your dictionary check faster, it might be quicker to select all the words from the dictionary which use the 8 letters first and then use that as your word list.

[Matt Vinyl]

Hmm, that's not a bad idea! Good optimisation there! Can have a seperate dictionary with just the 8 letter words in.

You're right though, itt is the smaller words that are the problem...

[admin]

Well, this took me longer than first expected!

Made a project that will find all words contained in source word, (source word can be any length and words of all lenghts will be found)

At the moment it takes around 1.5s to do a full search on my system, but I should be able to reduce this to about 0.2s by restricting the length of words searched.

See attatched file for demo project, with source.

[Ernest W. Quality]

You're talking about permutations (combinations are where the order doesn't matter).
If I start with an eight-letter word, ABCDEFGH, you want to know how many words of any length (3- can be made from those letters.
(By "word" here I don't mean a dictionary word, just some letters).
Let's also assume you are not allowed to use a letter more than once (changes the answer, but equally easy to do).

If I want to find how many 3 letter words can be made, then I have 8 choices for the first letter, 7 for the 2nd and 6 for the third. So the answer is 8x7x6, i.e. 8!/(8-3)!. Similarly for words of other lengths.

So the total number of possible words of lengths 3-8 that can be made from an 8-letter word is:
8!/5! + 8!/4! + 8!/3! + 8!/2! + 8! + 8! = 109536

(If two of the original letters were the same, this doesn't take into account duplicated words).

[Matt Vinyl]

Ah-hah!!! The Don!! Top stuff my man!!

You will certainly be included in the credits for this one!!

Will now delve into the code and convert it to 'Blitz' code (not using VB for this one, but essentially, there's only a few syntax changes to make!)

I'll have a pint waiting for you one day!