CODEWITHSUNDEEP
perlshuffle
ado
ado

Reputation: 1471

On Perl's List::Util's "shuffle" method. How to "unshuffle"?

I tend to use shuffle method to randomize the order of elements of a list. For example, here's a code that messes up roles for a little game:

 sub assign_roles {
       my ( $role_num_map ) = @_;
       my @roles;
       for my $role ( keys %$role_num_map ) {
         next if $role_num_map->{$role} == 0;
         push @roles, $role for ( 1 .. $role_num_map->{$role} );
       }
       my @shuffled_roles = shuffle @roles;
 }

My question is, how does "shuffle" randomizes the order? What method does it use? How can I go back from @shuffled_roles to $role_num_map ?

Upvotes: 1

Views: 287

Answers (1)

amon
amon

Reputation: 57620

shuffle randomizes the order. Thus, this operation cannot be reverted (much like you can't uncook a fried egg by putting it into the fridge). But we can use a trick: Shuffling indices instead of values:

my @items = 'a' .. 'z';  # things we want to shuffle
my @shuffled_idxs = shuffle 0 .. $#items;
my @shuffled = @items[@shuffled_idxs]; # using a slice to do the actual shuffling

From the @shuffled_idxs, we can make an array that allows reverse lookup:

my @reverse_idxs;
$reverse_idxs[$shuffled_idxs[$_]] = $_ for 0 .. $#shuffled_idxs;

# now we can use a slice to reverse the shuffling:
my @reversed = @shuffled[@reverse_idxs];

When we print out @items, @shuffled, and @reversed, we could get the following output:

abcdefghijklmnopqrstuvwxyz
hyaxruvnogekdzjmbpilstcqfw
abcdefghijklmnopqrstuvwxyz

This works fine for arrays. Your example is a bit different, because you have sequences like

a b b b c c

and you want to make the hash { a => 1, b => 3, c => 2 }. This can be done without unshuffling, using normal counting instead:

my %reversed;
$reversed{$_}++ for @shuffled_roles;

However, you skip over roles which map to zero. As this information is no longer present in the role array, it cannot be recreated.

Upvotes: 7

Related Questions