Re: Unique List

• To: mathgroup at christensen.cybernetics.net
• Subject: [mg397] Re: [mg358] Unique List
• From: perkins at colorado.edu (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.

Boulder, CO

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

>len=5;
>While[len != 6,
>               hand = Table[Random[Integer,{1,52}],{6}];
>               len = Length[Union[hand]]
>             ]
>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