MathGroup Archive 1995

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

Search the Archive

Re: Unique List

  • To: mathgroup at
  • Subject: [mg397] Re: [mg358] Unique List
  • From: perkins at (Tyler Perkins)
  • Date: Tue, 10 Jan 1995 18:30:45 -0700

Robert B. Love wrote
>OK, time for a little fun.  I can generate a list of random
>integers as    Table[Random[Integer,{1,42}],{6}] and I get a list 6
>elements long containing the integers from 1 to 42.  But how do I
>make sure no elements are repeated.

Ok, lemme give it a shot.  Notice that my code below does not rely upon any
special package, nor upon any iteration constructs like Table or While.  It
doesn't even use Function.  (Recursion is hidden within ReplaceRepeated.)
I love elementary solutions!

In[1]:= rules[range_, num_] = {
      Rule #1:
        Delete any repetition.  Append a new random number in its place.
    { s1___, e_, s2___, e_ } :> {       (* Only need to look at last one! *)
        s1, e, s2, Random[Integer, range]
      Rule #2:
        Otherwise append a new random number until long enough.
    {elems___} :> {elems, Random[Integer, range]} /; Length[{elems}] < num

In[2]:= {} //. rules[{1,42}, 6]

Out[2]= {34, 24, 13, 14, 9, 41}

In[3]:= In[2]

Out[3]= {22, 18, 39, 37, 14, 12}

In[4]:= In[2]

Out[4]= {35, 1, 7, 5, 34, 30}

... and so on.

        Tyler Perkins                   perkins at
        Boulder, CO

PS  It's good that Martin McClain's solution,

>While[len != 6,
>               hand = Table[Random[Integer,{1,52}],{6}];
>               len = Length[Union[hand]]
>             ]

is careful to not return a list which was returned from Union, since Union
returns a sorted list.  This would certainly not be a random sequence.
However, suppose we used a large number instead of 6.  It's very likely
that each long random sequence returned by Table[Random[...],...] will
contain at least one repetition.  It's possible that the above algorithm
would not terminate for a very long time!

An interesting question is, what is the order of this algorithm?  The order
of my solution should be O[num^2].

  • Prev by Date: Bin <-> Decimal conversion
  • Next by Date: Re: Get Parts of Expression by Position list
  • Previous by thread: Re: Re: Unique List
  • Next by thread: Re: Re: Suggestions needed for Mathematica course