Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re^4: Derangements iterator

by Anonymous Monk
on Dec 31, 2005 at 12:29 UTC ( #520136=note: print w/ replies, xml ) Need Help??


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

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ļ


Comment on Re^4: Derangements iterator
Download Code
Re^5: Derangements iterator
by Jedaļ (Initiate) on Dec 31, 2005 at 13:34 UTC
    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?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (3)
As of 2014-09-20 15:16 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (160 votes), past polls