Now here's my attempt to answer your two questions. I think I got it right but... well, I've been known to bang the hammer on my thumb so it wouldn't hurt to double check my logic.

Permutations of 7 distinct letters out of a set of 26 = P(26,7)=(26!)/(26-7)!

Permutations of 6 distinct letters and one blank out of a set of 26 letters and 1 blank = P(26,6) * C(7,1) * 26 = P(26,6) * 7! / (1!*(7-6)! ) * 26

General formula, with 26 letters, b blanks (maximum 7), and in the rack 7-b distinct letters and b blanks: P(26,7-b) * C(7,b) * 26^b. With no blanks, this reduces to the "permutations of 7 distinct letters" above, and with all blanks this is P(26,0)*C(7,7) * 26^7 = 26^7. I think this answers your first question.

Now, the situation where duplicate letters are allowed is that you have b blanks with duplicates allowed on the other 7-b letters. This is a similar situation to before, only instead of using the permutation formula P we use the multinomial coefficient, which is the number of distinct permutations in a multiset. The multinomial coefficient M(n1,n2,nk) is (n1 + n2 + ... nk)! / (n1!n2!....nk!). IE, with a rack of 5 (for simplicity) if you have 2 as and 3 bs, the number of distinct permutations is ( 2 + 3 )! / (2!3!) = 10. If instead of a and b you take any two distinct letters, the number of permutations increases to 10 * ( 26 * 25 ) = M(2,3) * P(26,2). So, for the general case of a rack of 7 with b blanks and the other 7-b letters some multiset, I think we have M(n1,n2...n sub7-b) * P(26,7-b) * C(7,b) * 26^b. If I'm right about this that answers your second question.

Perl module links that may be of interest:

Algorithm::Permute

Hope this helps... and I'll keep updating this if I figure anything more out. (Already updated several times to cull out less promising search avenues)

UPDATE: Fixed incorrect formula for adding wildcards to the distinct letter scenario.

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)!*26^b 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.

++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

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

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 );
[download]

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

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

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

  do {

  printf"%5d. ", ++$cnt;
  print"@list1\n"; # Display permutations

  } while( NextPermute( @list1 ) );

}
[download]

print"Counted $cnt unique permutations";
print $/;
[download]

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
[download]

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

Actually, I'm thinking it's a bit more complicated than that. Given seven unique letters, their permutations would be 7!. However, if you're allowed to pick any set of seven (unique) letters out of the alphabet, you would then have a domain of 26 * 25 * 24 * 23 * 22 * 21 * 20 possibilities. That's 3,315,312,000, but who's counting?

With a blank tile, you simply count that tile as one of the letters. The fact that it's blank is something of a red herring. If you're eliminating repeated letters, then the above product would simply have another element - you'd multiply it by 19, because you're just adding another tile, which cannot have any of the previously used letters. Only 19 letters are left. Conversely, if you *replace* one of the letter tiles with a blank one, you simply keep the same product.

On the other hand, if you're *allowing* the blank tile to represent any letter, including repeats, then you multiply your basic rack times 26, as many times as you have blank tiles. So, if your rack is 6 tiles and one blank, your answer is (26!/20!) * 26. Or, with A=size of alphabet, n= number of letter tiles, b = number of blank tiles, you would have: (A!/(A-n)!) * (b **A) (A ** b).

HTH.

Update: Corrected the order of the operands in the equation.

So, if your rack is 6 tiles and one blank, your answer is (26!/20!) * 26.

I think this formula is off by a factor of 7. This formula would be correct if the blank tile could only go into one position. However, the blank tile can go in any of seven positions, so it should be (26!/20!)*26*7. So, I still think the formula I gave in my answer above is the way to go.

UPDATE: Nah, I think spiritway is correct after all. Sorry!

No, because you're not adding a blank tile, you're *replacing* a letter tile with a blank tile.

Update:Alas, I think I've got it wrong, too. It looks like TedPride has it right...

1) Find all unique sets of letters given an input of letters and wildcards
2) Calculate the number of words for each unique set

The maximum possible number of letter sets is 26**wildcards, which means that you can comfortably fit all the letter sets in memory up to 4 wildcards. Scrabble only has 2 blanks, so this isn't a problem. Calculating the number of words possible from each set is a simple factorial / letter count operation. The following is a rough but workable solution, which you can edit as necessary for various letter / wildcard combinations.

use strict;
use warnings;

my $letters = 'ABCDEF??';

my $length = length($letters);

## We'll be using factorials a lot, so it's best to pre-calculate
my @factorial = (0,1);
$factorial[$_] = $factorial[$_-1] * $_ for 2..$length;

my ($blanks, @lsets, $lset, $nlset, $words, $twords);

## Find the number of blanks
while ($letters =~ /[^A-Z]/) {
    $letters =~ s/[^A-Z]//;
    $blanks++;
}

## Produce unique letter sets, given blanks
@lsets = ($letters);
while ($blanks--) {
    my %lsets;
    for $lset (@lsets) {
        for ('A'..'Z') {
            $nlset = join '', sort split //, $lset.$_;
            $lsets{$nlset} = ();
        }
    }
    @lsets = keys %lsets;
}

## Calculate the number of words possible from each letter set
for (@lsets) {
    $words = $factorial[$length];
    my %lcount;
    $lcount{$_}++ for split //, $_;
    for (keys %lcount) {
        $words /= $factorial[$lcount{$_}] if $lcount{$_} > 1;
    }
    $twords += $words;
}

print $twords;
[download]

Congratulations TedPride,

Your code works flawlessly for every possible scrabble set of letters I can think of.
You truly captured the essence of the problem and I learned a lot from your coding style.

Merci beaucoup!

Bernie

Instead of

## Find the number of blanks
while ($letters =~ /[^A-Z]/) {
    $letters =~ s/[^A-Z]//;
    $blanks++;
}
[download]

I find my $blanks = scalar ( my @blanks = ( $letters =~ /[^A-Z]/g ) ); more intuitive.

But, I like the other code a lot and am learning from it :)

That's even easier to do, given a file of dictionary words.

EDIT: I would like to add that if you have a small number of blanks (in this case, 2 or less), it is also possible to calculate the number of letter combinations from formulas. For 2 blanks:

Calculate number of letter sets with all unique letters
Calculate number of letter sets with one letter pair
Calculate number of letter sets with two letter pairs
Calculate number of letter sets with one letter triplet

Then you just need to calculate how many letter combinations can be made in each of the above cases for each letter set, multiply it out, and add up the results.