in reply to How to generate distinct random numbers?

You reduce randomness slightly my insisting on no duplication. Here's the code: 

sub distinct_random_int {
    my($num, $start,$end) = @_;
    my ($range, %nums) = $end - $start;
    if ($num < $range) {
        $nums{$start + int rand $range} = undef
            while keys(%nums) < $num;
        return keys %nums;
    }
    else {
        return;
    }
}

[download]
Storing in hash keys gets us uniqueness.

After Compline,
Zaxo

Replies are listed 'Best First'.
Re^2: How to generate different random numbers?
by Pragma (Scribe) on Sep 04, 2004 at 23:42 UTC
    No he doesn't. What he's actually asking for is a random shuffle. There are well known O(n) time and memory algorithms for that sort of thing. Look up Fischer-Yates.

    update: of course a shuffle won't work so well if the range is large

[reply]
      No he doesn't.
      I'm going to go ahead and disagree with you there, cowboy. Any time you impose a restriction on random, you've made it not random. A random shuffle of a known interval isn't a set of random numbers. Woe unto he who uses the "random" numbers for cryptographic purposes.

      thor

      Feel the white light, the light within
      Be your own disciple, fan the sparks of will
      For all of us waiting, your kingdom will come

[reply]
        Well since we're just arguing semantics, indeed, a random shuffle of a known interval isn't the same thing as a set of random numbers. But I never said they were the same thing. I merely said that it is not any "less random", and indeed it isn't.

        A random shuffle is really a random selection from a uniform distribution of the set of all possible permutations on that range of numbers (or N!).

        And who said the numbers had to be used for cryptographic purposes? You're adopting a very narrow view of things to make your case, pilgrim.

        Any time you impose a restriction on random, you've made it not random.
        Well this is just plain false (eg. if I restrict myself to a set of random even numbers, the numbers I've chosen are still random, and indeed, no less random). I think what you meant to say is that for cryptographic purposes, random numbers should only be chosen from a uniform distribution. This is an arguable proposition, especially since many distributions can be translated into one another, and thus any cryptographic function can transform a non-uniform distribution into a uniform one.
[reply]
Re^2: How to generate different random numbers?
by Rhys (Pilgrim) on Sep 05, 2004 at 00:52 UTC
    It might be more helpful to return shuffled ints between $start and $end, even if $num < $range. The user just won't get back $num ints. Perhaps the $range+1 returned value could be "Range too small."

    As for shuffle vs. rand, "use Benchmark". :-) See if there's a predictable threshold where one overtakes the other.

    Update: Is the ratio between $num and $range significant when determining whether a shuffle or rand is better to use? It would seems that a very small $num:$range ratio would benefit from rand, where shuffle-ing is better as $num:$range -> 1.

    Or am I speaking from a non-standard orifice?

[reply]
      hi johnnywang,
      As soon as you talk about 'distinct', 'random' goes out of the window. So i assume you need distinct numbers upon which you can't apply any pattern. The best way is to write a hash function on the current date + time which ofcourse must not give always increasing or decreasing numbers. Use google to find a suitable algorithm ( i am sure people have done it before).
[reply]

In Section Seekers of Perl Wisdom