MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Random choice

  • To: mathgroup at smc.vnet.net
  • Subject: [mg99840] Re: [mg99831] Random choice
  • From: Leonid Shifrin <lshifr at gmail.com>
  • Date: Fri, 15 May 2009 06:26:38 -0400 (EDT)
  • References: <200905150822.EAA18773@smc.vnet.net>

Hi Valeri,

RandomChoice  does not guarantee that all picked items (numbers) will be
different. In v.6,0+, use RandomSample:

In[1] = RandomSample[Range[500],100]//Short

Out[1] = {467,487,153,196,<<92>>,65,104,399,386}

For earlier versions, you can load Combinatorica:

In[2] = << DiscreteMath`Combinatorica`;

and use RandomPermutation:

In[3] = #[[Take[RandomPermutation[#], 100]]] &@Range[500]//Short

Out[3] = {120,122,328,6,241,<<90>>,291,58,409,314,109}

However, both methods will become very memory-hungry if your
upper limit is large enough (more than say 10^7), due to the necessity to
temporarily store an entire range of numbers. The used  memory
will be quickly released back to the OS, of course (Mathematica garbage
collector is quite good at this), but the peak load may be significant.

Here is the  version from my book (slightly modified)

( http://www.mathprogramming-intro.org/book/node514.html ),

which is free from this drawback. It works best  when the third optional
parameter  (updatenum) is about a quarter of the total numbers asked (n)
(this is a heuristics of course).


In[4] =

Clear[randomNumsOrdered];
randomNumsOrdered[numrange_List, n_Integer,
updatenum_Integer: 100] :=
Take[NestWhile[
    Union[Join[#, RandomInteger[numrange, updatenum]]] &,
    {}, Length[#] < n &], n];

For example,

In[5] = randomNumsOrdered[{1, 50000000}, 100] // Timing // Short

Out[5] = {0.,{292330,<<98>>,49669303}}

Finally, you may do it more systematically by constructing a binary search
tree (see Mathematica implementation, for example,  in R.Maeder "Computer
science with Mathematica") and then test each newly generated number against
those in the tree and insert if it isn't present already.
 But in practice, I doubt that this solution will be faster in Mathematica.

Hope this helps.

Regards,
Leonid


On Fri, May 15, 2009 at 1:22 AM, Valeri Astanoff <astanoff at gmail.com> wrote:

> Good day,
>
> Given this example :
>
> In[1]:= RandomChoice[Range[500], 100] // Union // Length
>
> Out[1]= 91
>
> what is the best way to get *exactly* 100 different
> random numbers ranging from 1 to 500 ?
>
> Any piece of advice would be appreciated.
>
> --
>
> Valeri Astanoff
>
>


  • References:
  • Prev by Date: Re: SparseArray and Compile
  • Next by Date: PlotLegend
  • Previous by thread: Re: Random choice
  • Next by thread: Re: Re: Random choice