Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot

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]
[ambrus]: Corion: two very hard things about presentations I should try to work on if I have twenty times as much free time as in real life are:
[Corion]: That's why I like HTML - it makes it relatively easy to resize stuff. Resizing with Powerpoint is much harder, or at least, I remember it being that way
[ambrus]: (a) good sans serif fonts optimized for slides in a projector with coverage of the symbols needed for mathematical formulas in a sans serif font matching the text font well, and
[ambrus]: (b) a good presentation system that lets the presenter quickly interactively edit the slides live during a presentation, to combine the advantages of blackboard and overhead slide styles in modern tech
[Corion]: Heh - in university, I cheated on (a) by doing blackboard presentations using chalk. But those were 2 hour presentations, not quick/essential/ reduced presentations where you want to show something quick
[ambrus]: (either on just one screen or two screens). this is necessary because
[ambrus]: overhead slide plus blackboard is inconvenient because the lighting conditions are different and they require separate areas you can't quickly repartition, and typing on keyboard is faster and more convenient than writing on a blackboard
[Corion]: (b) would be cool. I've thought about this doing Pod editing, and even simply regenerating/live updating the browser makes things much more interactive
[ambrus]: modern computers have way enough processing power to allow this, at least for geeks who are willing to spend a few weeks to learn a tricky new user interface like vim
[Corion]: ambrus: Well, for mathematical notation, I find blackboard much more convenient than a computer. But when inserting text or moving text around, the computer wins obviously

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (11)
As of 2017-09-26 10:18 GMT
Find Nodes?
    Voting Booth?
    During the recent solar eclipse, I:

    Results (293 votes). Check out past polls.