A naive approach for generating a set of random numbers – set means no duplications – is to repeat 1) pick a number, 2) ignore it if it is a duplicate, add it to the set otherwise. Obviously, this approach is not guranteed to stop because the same number can occur infinitely. You might argue that it wouldn’t because we are dealing with random, but such an argument is not plausible enough, because 1) computer deals with pseudo random, and because 2) it’s not beautiful solution.
Another approach is to enumerate numbers, say, 1 to 10, then shuffle them. After then, if we want a set of size 3, then we just pick 0th~2th element from the shuffled set. This approach suffer from a serious problem that we do not know how many times we have to shuffle it.
The following approach due to abraxsus(http://abraxsus.pe.kr) solves this problem. Following is the specific steps to get the set:
1) Generate all possible combination sets. And labels each of which like 1,2,3,…,n.
2) Pick a random number ranging from 1 to n.
3) Pick a set with the random number.
To illustrate, given [1,2,3,4,5], we generate all combinations like the following:
#1: [1,2,3]
#2: [1,2,4]
#3: [1,2,5]
…
#5C3: [3,4,5]
Then, generate a number between 1~5C3 and Pick a set labeled with that number.
Following is an implementation of above algorithm written in Ruby:
def v_0_set(list, r)
v_i_set(list, -1, 0, r)
end
def v_i_set(list, prev_val, idx, r)
start_idx = prev_val + 1
end_idx = (list.size – 1) – (r – 1 – idx)
(start_idx..end_idx).inject([]) do |memo, val|
memo << [val]
end
end
def gen_comb(list, r)
current_set = v_0_set(list, r)
for i in (1..r-1)
current_set = gen_comb_with_previous_value_set(list, current_set, i, r)
end
current_set.map do |idx|
idx.map { |i| list[i] }
end
end
def gen_comb_with_previous_value_set(list, prev_set, idx, r)
prev_set.inject([]) do |memo, prev_val|
memo += cart_prod(v_i_set(list, prev_val[-1], idx, r), prev_val)
end
end
def cart_prod(list, val)
list.inject([]) do |memo, i|
memo << val + i
end
end
def rand_seq_gen_without_duplicates(min, max, r)
gen_comb((min..max).to_a, r)[rand(max + 1) + min]
end
for i in (1..10)
puts rand_seq_gen_without_duplicates(5, 10, 3).inspect
end
[/code]
Obviously, above description and program are not good enough simply because there might be better way to generate a combination. We might be able to pick a combination given a random number. However, that's beyond the scope of this article. Interested readers should consult another book (like Art of Computer Programming, Volume 4, Fascicle 2, The: Generating All Tuples and Permutations:1/e).
Leave a Reply