Re: Derangements iterator

[Roy Johnson]

Producing a single derangement (such as might be needed for a Secret Santa list) is just a matter of doing a rotation. Of course, you'd want to randomize the order first, to keep things secret:

use List::Util 'shuffle';
my @from = shuffle(@ARGV);
print "$from[$_-1] => $from[$_]\n" for 0..$#from;

[jdporter]

That doesn't guarantee that the constraint of derangement is met. Example scenario:

 1 2 3   # original
 2 1 3   # shuffled
 1 3 2   # rotated one place to the left.

[Roy Johnson]

You misunderstood what was being deranged. What you list as the original is not the original, but merely the (unordered) set. Shuffling provides the "original" order, and rotation provides the derangement of that order.

[Anonymous Monk]

We can just use the shuffle algorithm slightly modified to suit our needs :

use Inline C => <<'END_OF_C_CODE';

void cderange(SV* array_ref) {
  AV* array;
  I32 index, i;
  SV** sv_1, **sv_2;
  SV* sv_temp;

  if (! SvROK(array_ref))
    croak("array_ref is not a reference");

  srand(time( NULL ));
  array = (AV*)SvRV(array_ref);
  index = av_len(array);
  for (; index; index--) {
    i = (I32) (rand() % (index));
    sv_1 = av_fetch(array, index, 0);
    sv_2 = av_fetch(array, i, 0);
    sv_temp = *sv_1;
    *sv_1 = *sv_2;
    *sv_2 = sv_temp;
  }
  return;
} 

END_OF_C_CODE 

sub derange {
  my $first = $_[0];
  cderange \@_;
  if( $first eq $_[0] ){
    ($_[0], $_[1]) = ($_[1], $_[0])
  }
  return @_;
}

This is fast, but don't work very well with very big arrays (size over RANDMAX, usually 32000).

--
Jedaļ