Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much

Re^3: Derangements iterator

by Roy Johnson (Monsignor)
on Dec 29, 2005 at 19:14 UTC ( #519832=note: print w/replies, xml ) Need Help??

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

    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://519832]
[perldigious]: Just kidding. Thanks 1nickt, I'll go ahead and do it the right way. An extra set of brackets and a little extra indentation isn't too much to ask.
[karlgoethebier]: perldigious: perhaps a block if you are paranoid ;-)
[choroba]: but undef %hash and %hash = () both work, too, but the first one keeps the memory allocated, while the latter makes it available for other parts of the program.
[choroba]: iirc
[perldigious]: karlgoethebier: Well it is a pretty old and complicated (for me) bit of code I wrote (poorly by my current standards), so I'm expecting everything to break when I add the scoping and find out what else is undesireably scope changed. :-)
[perldigious]: Ah, thanks choroba, that sort of thing was precisely what I was wondering when I asked.
[perldigious]: I didn't want to tie up memory unecessarily basically, I wanted to "delete" it specifically to free it up, and wasn't sure I was even accomplishing that.

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (8)
As of 2017-07-21 19:51 GMT
Find Nodes?
    Voting Booth?
    I came, I saw, I ...

    Results (335 votes). Check out past polls.