Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling

Re^2: Derangements iterator

by jdporter (Canon)
on Dec 29, 2005 at 19:09 UTC ( #519831=note: print w/ replies, xml ) Need Help??

in reply to Re: Derangements iterator
in thread Derangements iterator

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.
We're building the house of the future together.

Comment on Re^2: Derangements iterator
Download Code
Replies are listed 'Best First'.
Re^3: Derangements iterator
by Roy Johnson (Monsignor) on Dec 29, 2005 at 19:14 UTC
    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.

      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).

        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
        Very fast, but this code is subject to the same caveat as Algorithm::Numerical::Shuffle.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://519831]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (9)
As of 2015-11-26 09:53 GMT
Find Nodes?
    Voting Booth?

    What would be the most significant thing to happen if a rope (or wire) tied the Earth and the Moon together?

    Results (696 votes), past polls