yoda54 has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks,

I can't seem to put this in code, perhaps its too much intoxication lately... :) I have a bunch of objects with a $objref->randomturn() method. What I need is each object to act in lowest to highest order. In the event that X number of objects draw the same number, those X objects need to re-draw until they have drawn a unique number. I am storing all my object references in an array, so I'm thinking about something like this.

As usual thanks for any help!

package SOMECLASS;

sub new { blah blah blah }

sub randomturn {
    my $self = shift @_;
    my $random = int(rand(2000));
    return $random;
}

1;


package main;

use SOMECLASS;

my $array;

#gen objects
for(1..100) {
    push @$array, SOMECLASS->new();
}


foreach (@$array) {

    #build some data structure to store 1) drawn number 2) object refe
+rence 3) turn order ?

    #generate turn order, use recursive function to redraw until there
+ is no tie
    $_->randomturn();  
}

#Finally...
#sort data structure &

foreach(@$turnorder) {   # @$turnorder or whatever data structure...
    $_->dosomething();
}

[download]

Replies are listed 'Best First'.
Re: Algorithm help needed.
by GrandFather (Saint) on Jul 23, 2006 at 22:45 UTC

    I'd be inclined to turn the problem around. Build a list of all the ogjects that are in the queue. Randomise the queue. Draw the objects out one at a time.

    If the objects need to know what their position in the queue is run over the queue after it's been randomised and tell the objects what their turn number is.

    Super Search for titles containing "random array" in SoPW for a huge number of threads asking how to generate a randomised list or how to pick a random entry from a list.

    Update: A simple way to do it is:

    my $array;
my @queue;

#gen objects
push @$array, SOMECLASS->new() for 1..100;

#generate random ordered queue
push @queue, splice @array, int rand @array, 1 while @array;

#process
$_->dosomething () foreach @queue;

    [download]

    The down side is you lose the original ordering and splicing stuff randomly out of a huge list may slow things down a little. For a small list or occasionally it shouldn't be a problem.

    DWIM is Perl's answer to Gödel
[reply]
[d/l]
      This is also called a shuffle, and super-searching for that (or reading Knuth) will give you some very efficient algorithms for doing it.

      --
      sgifford's Web page
[reply]

      As I was taught, splice is very inefficient way of implementing a shuffle.

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]

Back to Seekers of Perl Wisdom