Re^4: Derangements iterator

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

in reply to Re^3: 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ļ

Replies are listed 'Best First'.
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.

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 lurking in the Monastery: (8)
As of 2021-04-14 21:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?