there is only one possible solution

I count 7! = 5,040 solutions.

Trying 1e15 shuffles

There are 15!/8! = 32,432,400 permutations of the set (and for that matter 15! is only about 1.3e12). I don't see mention in Algorithm::Permute of how it handles duplicate elements, but I know that Algorithm::Loops handles them correctly.

That said I do agree with the thrust of your point. :)

I briefly looked at Algorithm::Loops by tye this morning but didn't quite understand it yet. Not quite intuitive I would say. BTW, my mathematical understanding is poor. Why is it 15!/8!?

.

«The Crux of the Biscuit is the Apostrophe»

NextPermute() and NextPermuteNum() modify the input array in place, and (to traverse all permutations) require that the input starts off sorted. So minimally adapting your previous code to use Algorithm::Loops would look (untested) something like this:

#!/usr/bin/env perl

use strict;
use warnings;
use Algorithm::Loops qw(NextPermuteNum);
use Data::Dump;
use feature    qw(say);

my @n = sort { $a <=> $b } ( 1, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8,
+ 11, 12, 13, 14, 14, 15 );

my $m3 = qr/(.)\1\1/;
my $m2 = qr/(.)\1/;

do {
    my $s = pack( "(A*)*", @n );
    if ( $s =~ /($m3)/ ) {
        say $1;
        sleep 1;
        goto PERMUTE;
    }
    if ( $s =~ /($m2)/ ) {
        goto PERMUTE;
        say $1;
        sleep 1;
    }
    say join " ", @n;
  PERMUTE:
    ; # empty statement to attach the label to
} while (NextPermuteNum( @n ));

__END__
[download]

As for the 15!/8! figure: imagine each of the 1s is a different colour, then there are 15! distinguishable ways to arrange the numbers. Take any one of those (valid solution or not) and it has 8 coloured 1s in some order; and each of the 8! ways to order those colours will appear once in what is otherwise the same arrangement of numbers.

15! is the number of ways to sort 15 different elements.

But you have 8 identical 1 which would always create 8! duplicates for each solution by swapping 1s (well rather symmetries or congruence classes)

hence 15!/8!

update

WP has nice graphics visualizing it

https://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets

Cheers Rolf
_{(addicted to the Perl Programming Language :)
see Wikisyntax for the Monastery}

Darn!1!

> I count 7! = 5,040 solutions.

Of course you are right, what my my brain saw was that there is only one possible way to position the 1s.°

What I should better have shown is

(1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2)

which has only one solution

(1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1)

and 15! divided by 7! is still a very big number.

> I don't see mention in Algorithm::Permute of how it handles duplicate elements,

Assuming worst case means it's not handling duplicates differently. Many hear just use shuffle which certainly doesn't care.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
see Wikisyntax for the Monastery}

°) off by one permutation group ;)

karl@h3002993:~/src/perl$ time ./pmute.pl
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

real    0m0,064s
user    0m0,044s
sys     0m0,005s
[download]

«The Crux of the Biscuit is the Apostrophe»

So this aren’t valid permutations?

karl@h3002993:~/src/perl$ ./pmute.pl
1 8 1 2 1 7 1 3 1 6 1 5 1 4 1
karl@h3002993:~/src/perl$ ./pmute.pl
1 3 1 4 1 7 1 5 1 2 1 6 1 8 1
karl@h3002993:~/src/perl$ ./pmute.pl
1 4 1 8 1 6 1 5 1 3 1 2 1 7 1
karl@h3002993:~/src/perl$ ./pmute.pl
1 5 1 8 1 2 1 4 1 6 1 3 1 7 1
karl@h3002993:~/src/perl$ ./pmute.pl
1 7 1 5 1 4 1 3 1 8 1 2 1 6 1
[download]

FYI

karl@h3002993:~/src/perl$ time ./pmute.pl
1 4 1 3 1 2 1 6 1 5 1 7 1 8 1

real    0m0,081s
user    0m0,076s
sys     0m0,004s

karl@h3002993:~/src/perl$ lscpu
 Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Address sizes:       46 bits physical, 48 bits virtual
Byte Order:          Little Endian
CPU(s):              1
On-line CPU(s) list: 0
Vendor ID:           GenuineIntel
Model name:          Intel(R) Xeon(R) CPU E5-2680 v3 @ 2.50GHz
…
[download]

> So this aren’t valid permutations?

They are. Mea culpa.

You are listing the permutations of the fillers between the fixed 1s, hence 7! valid solutions.

See Re^8: Algorithm RFC: fast (pseudo-)random shuffle with no repetition for what I meant and try (1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2) instead.

If this doesn't convince you that try-and-error isn't a good idea, try adding even more 1s and 2s.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
see Wikisyntax for the Monastery}

Somehow I also calculate differently:

CL-USER> (expt 10 15)
1000000000000000
CL-USER> (* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)
1307674368000
[download]