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].