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.
Tyler Perkins perkins at colorado.edu
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].