http://www.perlmonks.org?node_id=1057028

in reply to Re^5: Challenge: 8 Letters, Most Words
in thread Challenge: 8 Letters, Most Words

> In other words, choose all combinations of any 8 chars out of the following string: "aaaabbbcccddddeeeeffffgggghhhiiijjkkkllllmmmnnnnoooopppqrrrrssssstttuuuuvvwwwxxyyyzzzz"

The point is to handle duplications, if all letters are unique the answer is simply (26 over 8)

```  DB<288> sub fac {my \$x=1; \$x*=\$_ for 2..\$_[0]; \$x}

DB<289> sub binom { my (\$n,\$k)=@_; fac(\$n)/(fac(\$n-\$k)*fac(\$k)) }

DB<290> binom 26,8
=> 1562275

Reasoning is simple, it calculates all binary vectors of length 26 with exactly 8 1-bits.

But with duplications its more complicated, e.g. 4 out of "aabcd" is not (5 over 4)=5

```a bcd
abcd
aa cd
aab d
aabc

cause the first 2 solutions are identical.

Generating all combinations and filtering the unique once is normally not very clever, cause the overhead can be enormous.

```  DB<292> length "aaaabbbcccddddeeeeffffgggghhhiiijjkkkllllmmmnnnnoooo
=> 86

DB<293> binom 86,8
=> "53060358690"

And I'm stuck finding a formula which calculates all unique solutions, but generating is easier, just don't allow bitvectors with "gaps" between identical letters:

so

``` "aaaabbbc..." # pattern
"1000100...." # ok      => ab...
"1100100...." # ok      => aab...
"1001100....  # not ok  => aab...

I will update this post with a loop generating all possibilities soon.

##### update

indeed L~R's number of 12461993 possibilities is correct

The following (non-optimized) code took 3 minutes to calculate them:

```use strict;
use warnings;
use Data::Dump qw/pp/;

my %max=(
a => 4,
b => 3,
c => 3,
d => 4,
e => 4,
f => 4,
g => 4,
h => 3,
i => 3,
j => 2,
k => 3,
l => 4,
m => 3,
n => 4,
o => 4,
p => 3,
q => 1,
r => 4,
s => 5,
t => 3,
u => 4,
v => 2,
w => 3,
x => 2,
y => 3,
z => 4,
);
my \$maxword=8;

#%max=(a=>2,b=>1,c=>1,d=>1);
#\$maxword=4;

my @keysort=sort keys %max;

my \$nsolutions=0;

sub generate {
my (\$idx,\$word)=@_;
#pp \@_;

return if \$idx >= @keysort;

my \$newword;

my \$key= \$keysort[\$idx];
for my \$n (0..\$max{\$key}){
#    print "\t"x\$idx ,"\$n x \$key\n";
my \$newword = \$word.(\$key x \$n);

if (\$maxword== length \$newword) {
#      print "-> \$newword\n";
\$nsolutions++;
last;
}

generate(\$idx+1, \$newword  )
}
}

generate(0,"");

print \$nsolutions;