in reply to Re^2: Algorithm RFC: fast (pseudo-)random shuffle with no repetition
in thread Algorithm RFC: fast (pseudo-)random shuffle with no repetition

It seems like that is actually a bit unwieldy. Another try:


#!/usr/bin/env perl

use strict;
use warnings;
use Algorithm::Permute;
use Data::Dump;
use List::Util qw(shuffle);
use feature    qw(say);

my @n = shuffle( 1, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 11, 12, 13,
+ 14, 14, 15 );
my $p = Algorithm::Permute->new( \@n, 20 );

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

PERMUTE: {
    my @r = $p->next;
    dd \@r;
    my $s = pack( "(A*)*", @r );
    if ( $s =~ /($m3)/ ) {
    # say $1;
    # sleep 1;
        goto PERMUTE;
    }
    if ( $s =~ /($m2)/ ) {
        # say $1;
        # sleep 1; 
        goto PERMUTE;
    }
    say join " ", @r;
}

__END__

[download]

Minor update: Fixed dead code.

«The Crux of the Biscuit is the Apostrophe»

  • Comment on Re^3: Algorithm RFC: fast (pseudo-)random shuffle with no repetition
  • Download Code

Replies are listed 'Best First'.
Re^4: Algorithm RFC: fast (pseudo-)random shuffle with no repetition
by LanX (Saint) on Sep 24, 2023 at 12:28 UTC
    A good algorithm must not fail on edge cases.

    One can easily find many where there are no or only few solutions.

    Now try blindly guessing permutations, till you find the only possible solution for ( (1)x8 , 2..8 )

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

[reply]
[d/l]

      Do you mean like this (1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8)? Because then I actually get more results quickly. However, something is not quite right with the regular expressions. I must be swapping $m3 with $m2. This is a bit of a mystery to me at the moment.

      «The Crux of the Biscuit is the Apostrophe»

[reply]
[d/l]
[select]
        I didn't run your code, and I don't trust it either.

        But I assumed you wanted a brute force try and error shuffling.

        > Do you mean like this (1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8)

        Yes.

        And there is only one possible solution

        (1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1)

        Trying 1e15 shuffles to finally get there seems like a good way to transform your hardware into an electric heater only.

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

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom