Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: Scrabble word arrangements with blank tiles

by Moriarty (Abbot)
on Nov 14, 2005 at 04:36 UTC ( #508208=note: print w/ replies, xml ) Need Help??


in reply to Scrabble word arrangements with blank tiles

I may be getting a little confused here, but, if the number of combinations with 7 unique letters is 7! then the number of combinations with 6 unique letters plus a blank should be 6!*26, and with 5 unique letters and 2 blanks would be 5!*26*26 making the formula (n-b)!*26b where n equals the number of tiles and b equals the number of blanks.

Of course this formula doesn't work for the case where all the tiles are blanks.


Comment on Re: Scrabble word arrangements with blank tiles
Re^2: Scrabble word arrangements with blank tiles
by Zaxo (Archbishop) on Nov 14, 2005 at 05:35 UTC

    ++Moriarty for boiling this down nicely.

    Of course this formula doesn't work for the case where all the tiles are blanks.

    But it does! Little-known fact: 0! is 1.

    After Compline,
    Zaxo

Re^2: Scrabble word arrangements with blank tiles
by spiritway (Vicar) on Nov 14, 2005 at 05:46 UTC

    The number of combinations with 7 unique letters is not 7!, unless you simply are trying to arrange 7 unique tiles that already have been chosen. However, I understood the OP's question to involve 7 unique tiles, chosen from a total of 26 possible letters, which gives a different equation. That equation would be 26 * 25 * 24 * 23 * 22 * 21 * 20. Your first tile could be one of 26 possible letters. Since repeats were excluded, the next tile could only have 25 possibilities - the first chosen letter is "taken". And so on. This equation becomes (A!)/(A-n)!, where the variables are as I described above.

    If the blank tile can be *any* letter, including ones that have already been chosen, then you simply multiply by 26, as many times as you've got blank tiles. If the blank tile must also be unique, the it works a though it were just another tile with a letter on it.

    When the tiles can all be chosen without regard to whether there is repetition (or when they're all blank), the equation becomes simply A ** n, where A is the size of the alphabet, and n is the number of tiles.

      Actually, if I'm reading the OP correctly, they already have the 7 unique tiles and want to know how many possible combinations they can make from them, which would be 7!

      If you replace one with a blank, the number of combinations depends on the rules for the blank. If the blank can only be one of the remaining letters, then the number of combinations becomes 7! * 20. If, however, the blank can be any letter, including any of the other 6 chosen, the formula becomes more complex, as you would have 7! * 26 minus any duplicates (I haven't worked out how to calculate the number of duplicates that would be involved).

Re^2: Scrabble word arrangements with blank tiles
by Moriarty (Abbot) on Nov 14, 2005 at 06:14 UTC

    The more I think about it, the more I think I've got it completely wrong, but then, I think the OPs figure are also wrong

    Looking at the simplest of the OPs figures, 2 tiles where one is blank, there must be at least 76 unique combinations ('A' | blank, 'A' + blank and blank + 'A' where bank can't equal 'A') so I can't see how the OP came up with their figures.

    I haven't come up with a formula to match this premise as yet, but I'm sure my original formula is totally wrong. I would like some clarification from the OP before I try to figure out the correct formula.

      To clarify the problem, assume we are trying to arrange 7 tiles that already have been chosen.
      ABCDEFG generates 7! = 5,040 unique permutations
      ABCDEF? generates 115,920 unique permutations and not 6!*26=18,720
      ABCDE?? <-- This is the stumper!

      The keyword is "unique" permutations.

      For example, permuting ABC? where ? represents a blank tile A..Z results in 624 arrangements but only 588 are unique permutations. Duplicate arrangements like AABC AABC AACB AACB ABAC ABAC ABBC ABBC ... must be culled to get the unique set.

      Algorithm-Loops has a neat permute function which I used to check racks with one blank tile.
      It generates the unique permutations that I am looking for.
      Here is an example for a simple rack AB?:

      use strict; use Algorithm::Loops qw( NextPermute );

      my @list= sort ('A'..'B'); # Find unique permutations for AB? my $cnt; my @list1;

      # $l represents one blank tile cycling thru all letter values for my $l ('A'..'Z') {

      @list1 = sort(@list,$l); # Very important to sort print"@list1\n"; # Show what's happening

        do {

      printf"%5d. ", ++$cnt; print"@list1\n"; # Display permutations } while( NextPermute( @list1 ) ); }

      print"Counted $cnt unique permutations"; print $/;

      prints:

      A A B 1. A A B 2. A B A 3. B A A A B B 4. A B B 5. B A B 6. B B A A B C 7. A B C 8. A C B 9. B A C 10. B C A 11. C A B 12. C B A A B D 13. A B D 14. A D B 15. B A D 16. B D A 17. D A B 18. D B A ... ... ... Counted 150 unique permutations

      Any suggestions on how to code this for 2 blank tiles without getting "Out of memory" failure?

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://508208]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (10)
As of 2014-08-21 19:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (143 votes), past polls