http://qs321.pair.com?node_id=519832


in reply to Re^2: Derangements iterator
in thread Derangements iterator

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.
Caution: Contents may have been coded under pressure.

Replies are listed 'Best First'.
Re^4: Derangements iterator
by Anonymous Monk on Dec 31, 2005 at 12:29 UTC

    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 @_;
}

    [download]

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

    --
    Jedaļ
[reply]
[d/l]
      Oops.. Sorry, the wrapper performs unnecessary operations, here a good version : 
      use Inline C => <<'END_OF_C_CODE';

void cderange ( SV* truc, ... ){
  SV* sv_temp;
  I32 index, i;
  Inline_Stack_Vars;

  srand(time( NULL ));
  index = Inline_Stack_Items;
  for (; index; index--) {
    i = (I32) (rand() % (index));
    sv_temp = Inline_Stack_Item(index);
    Inline_Stack_Item(index) = Inline_Stack_Item(i);
    Inline_Stack_Item(i) = sv_temp;
  }
  Inline_Stack_Done;
}

END_OF_C_CODE

      [download]
      Very fast, but this code is subject to the same caveat as Algorithm::Numerical::Shuffle.
[reply]
[d/l]

In Section Cool Uses for Perl