Random numbers without repeats

Posted on 2008-11-18 09:41 By alexiocowabunga (

17)

Categories:

How do I ...? with Maple

I want to generate a set of numbers of fixed size with maple, when I use the rand procedure within a fixed integer range let us say rand(1..2^4) and ask maple to pick 8 integers, maple will pick 8 different integers in the required range.

I would be grateful for any help.

Alex

To avoid repeated elements,

Comment on 2008-11-18 10:09 from Thomas Unger (

79)

To avoid repeated elements, one could use the member command to check if the element is already in your list/set.

Thomas

random numbers without repeats:procedure.

Comment on 2008-11-18 11:03 from xavier (

33)

I found a solution:

f := proc (n, a, b) local A, x; A := []; if n <= b-a+1 then A := [`mod`(rand(),b-a+1)+a]; while nops(A) < n do x := `mod`(rand(),b-a+1)+a; if not member(x,A) then A := [op(A), x] end if end do end if; return A end proc;

f(8,1,2^4);
[10, 7, 2, 12, 1, 11, 6, 9]

a more simple approach

Comment on 2008-11-18 11:25 from Thomas Unger (

79)

a set eliminates double elements by itself.

S:={}:while nops(S)<10 do S:=S union {rand(1..100)()}; end do:

{3, 12, 19, 40, 49, 51, 53, 63, 67, 90}

using RandomTools

Comment on 2008-11-18 12:03 from Doug Meade ( Maple Rating 4

739)

The rand command has been updated and upgraded with the introduction of the RandomTools package. You really should check it out.

Here's how I would approach your problem. The general idea is similar to Thomas Unger's. In my implementation, the arguments to the procedure are the number of distinct elements and the set from which they are to be chosen. This needs some checking to be sure the set has enough elements to choose n unique members, otherwise it would be an infinite loop. You can do that for yourself (or ask again if you need more help). Anyway, here's my code and a couple of examples:

f := proc( n, S )
  uses RandomTools;
  local A;
  A := Generate( set(choose(S),n) );
  while nops(A)<n do
    A := A union Generate( set(choose(S minus A), 8-nops(A) ) )
  end do;
  return A;
end proc:
f(8,{$1..2^4});
                        {4, 6, 8, 10, 11, 13, 14, 15}
f( 3, {red,blue,green,brown,yellow,gold,bronze,silver,orange} );
                             {red, blue, green}

I hope this is helpful,

Doug

---------------------------------------------------------------------
Douglas B. Meade  <><
Math, USC, Columbia, SC 29208  E-mail: mailto:meade@math.sc.edu       
Phone:  (803) 777-6183         URL:    http://www.math.sc.ed

randcomb, randperm

Comment on 2008-11-18 12:07 from Joe Riel ( Maple Rating 4

1260)

That's clever, however, it isn't clear whether the OP wants a random permutation or a random combination. Note that the order of a set of integers is not random.

A simpler way to pick a random combination is to use combinat:-randcomb:

combinat:-randcomb([seq(1..20)], 10);
                      [2, 4, 5, 6, 8, 12, 13, 15, 17, 18]

combinat:-randperm can be used to pick a random permutation, then select just the desired 1..n elements from it, however, if the size of the sublist is a small fraction of the size of the permutation, the method is less efficient. A better approach is to combine the two:

f4 := proc(n,a,b)
uses combinat;
    randperm(randcomb([seq(a..b)],n));
end proc:

Thank you all

Comment on 2008-11-18 12:59 from alexiocowabunga (

17)

Thanks for all your responses, I only just popped out to lunch and came back to a great set of replies.

I know what to do now, they are all good ways to approach the problem, especially the randcomb argument.

okay, a time test also

Comment on 2008-11-18 13:06 from Thomas Unger (

79)

okay, a time test also showed that Joe's method works much faster than mine. Building up a set with union takes its time.