## Generating a set of random numbers

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

Similar Posts:

1. JM wrote:

>> This approach suffer from a serious problem that we do not know how many times we have to shuffle it.

이부분은 잘 모르겠는데요. 셔플이 임의의 원소 두개를 계속 스왑하는 과정으로 이루어진다면 모르겠지만 꼭 그럴 필요는 없죠. :)

A = [1,2,3,4,..,N]
for i = 1 to N do swap(A[i], A[rand(i..N)])

첫번째 자리에는 모든 숫자가 1/N 의 확률로 출현할 수 있고, 두번째 자리에는 나머지 숫자들이 각 1/(N-1) 의 확률로 출현할 수 있고.. std::random_shuffle 도 이 방법으로 구현되어 있다고 기억하는데, 아마 TAOCP Vol 2 에 나올 겁니다. 결과로 N! 의 permutation 이 모두 같은 존재 확률을 갖죠.. 고로

vector genRandSet(int n, int r)
{
vector perm;
for(int i = 0; i = 0; –i) swap(perm[i], perm[rand() % (i+1)]);
perm.erase(perm.begin() + r, perm.end());
return perm;
}

정도면 괜찮은 답이 되지 않을까요? (컴파일도 안해봤지만 -_-)
두번째 for 문은 std::random_shuffle(perm.begin(), perm.end()); 로 대체할 수도 있겠네요. :3

Posted 17 Jun 2006 at 6:24 pm
2. JM wrote:

아니…. vector<int> 등이 HTML 태그로 인식되어서 깨져버리는군요. 이궁..

Posted 17 Jun 2006 at 6:26 pm
3. JM wrote:

다시 코드만..
vector<int> genRandSet(int n, int r)
{
vector<int> perm;
for(int i = 0; i < n; ++i) perm.push_back(i);
for(int i = n-1; i >= 0; –i) swap(perm[i], perm[rand()%(i+1)]);
perm.erase(perm.begin() + r, perm.end());
return perm;
}

Posted 17 Jun 2006 at 6:27 pm
4. MKSeo wrote:

종만님 하이.

for i = 1 to N do swap(A[i], A[rand(i..N)])
오 이거 나이스해요 ㅎㅎ

Posted 17 Jun 2006 at 7:58 pm
5. abraxsus wrote:

나이스! vol.2에 나옴. 좋네!
이건 random permutation을 구하는거다..
만약 for문의 N을 N보다 작은 k로 바꾸고 배열에서 앞부분 k개만을
취한다면, random combination을 구하는 알고리즘으로 변신하게 된다.
역시 굿!
딴지좀 걸자면, 이렇게되면 바로 나의 첫번째 답안과 같은게 된다-_-;; 그치 않냐..
그리고 random combination을 원한다면 N이 클수가 있으므로 구태여 배열을
쓰지 않아도 될테고, O(k^2)로 예상한 답안이 바로 이거다.. 컹~
그러나 암튼 random permutation구하기로는 딱 좋은 알고리즘같구나..

Posted 18 Jun 2006 at 3:33 am
6. JM wrote:

k가 N에 근접할 수록 다음 숫자를 고를 수 있는 확률이 낮아지기 때문에.. candidate set 을 유지하지 않는다면.. 각 iteration 의 expected time 은 점점 커지게 됩니다. 극단적으로 k = n-1 이라고 두었을때, 마지막 숫자를 고르기 위한 expected throw 는 n번이 되겠고, 마지막 phase 에만 O(nk) = O(k^2) 의 시간이 들겠죠..

물론 k*2 > n 이면 k = n-k 로 리셋한다 등의 꽁수를 부릴 수도 있겠습니다만, 그렇다 해도 expected time complexity 가 O(k^2) 로 나올거 같진 않네용~

Posted 18 Jun 2006 at 12:26 pm
7. abraxsus wrote:

JM님. 에구. 무슨 말씀이신지 잘 이해가 안가네요.
제가 생각한 구현은 이와는 좀 다른거였읍니다.. O(k^2)라한것은 이 알고리즘에 대한
얘기가 아닌거지요.. :-)
여기선 배열을 썼지만, 제 생각에는 일반적으로 N이 무지 크고 k는 그다지 크지 않기
때문에 제가 생각한 구현은 거꾸로 지금까지 선택된 숫자들만 메모리에 올리는
방식이기에, 그리고 다음 숫자를 선택한후 지금까지 선택된 숫자들과 비교해서 조정하는
방식이라서 그렇습니다..
이 알고리즘은 random permutation을 구하기엔 아주 좋은거 같습니다만..
제가 원래 고민하던것은 random combination을 구하는것이고, N이 크다고 가정했기에
그런 알고리즘을 생각하게 된것이고요..

Posted 18 Jun 2006 at 1:27 pm
8. abraxsus wrote:

뜬금없는 얘기같지만, TAOCP를 읽다가…
무지하게 큰 N이 있읍니다. (n! 같은..) 1~N사이의 랜덤값을 얻기위해
rand(1~N)을 구하는것과 그보다 작은 범위의 여러개의 랜덤값을 구해서 그것들을 조합하는것,
예를 들어 각 자리수를 따로 구해서 붙여버린다든지..

과연 후자가 더 좋은 random을 제공할까요??
이건 우리가 쓰는 random generator의 성능에 대한 문제제기이기도 하지만,
즉 그냥 random generator의 성능에 달렸다..라고 답하면 끝날지 모르겠지만..
후자가 더 좋을것만 같은 이 느낌은 뭔지-_-;;;

Posted 18 Jun 2006 at 1:48 pm
9. MKSeo wrote:

두분 대화에 대한 follow up 이 안되네요 ㅎㅎ
이해가 잘;;;

암튼 taocp, jm, abraxsus 파이팅!! ㅋㅋ

Posted 18 Jun 2006 at 6:03 pm
10. JM wrote:

리플이 길어지네요..-_-;

1.
아. 선택된 숫자들만 메모리에 올린다는 것은 이해했는데요^^ 저는 랜덤하게 숫자를 골라가면서 중복이 발생하면 다시 던지는 거라고 생각했었어요. 루프가 진행될 수록 이미 택한 숫자가 나올 확률이 커지니까 새 숫자를 고르기 위해 주사위를 던져야 할 expected 횟수가 늘어난다는 얘기였죠. N/2 번째 숫자를 고를 때는 1 * 1/2 + 2 * 1/4 + 3 * 1/8 + .. 이 될 테니까요. -_-;

k에 비해 N이 엄청 큰 경우라면, 새 자리에 들어갈 수 있는 숫자의 목록 대신 들어갈 수 없는 숫자의 목록을 저장해서 O(k^2) 시간에 답을 구할 수 있겠네요. ㅎㅎ

2.
그리고 index 를 랜덤으로 주었을 때 index -> combination 을 구하는 함수라면 최대 amortized O(n+k) 시간에 동작하게 되지 않을까 하는데요. @_@

3.
저도 TAOCP 를 제대로 읽어본 것은 아니라~ 음.. 슈도랜덤함수의 질을 평가한다던가 하는 주제에 대해서는 아는게 없어요. 조합이 어떤 형식이 될지 모르지만, 조합이 덧셈이나 곱셈만 아니라면 이론적으로 비슷한 랜덤이 나와야 하지 않을까요? n비트 랜덤 정수를 얻기 위해 n번 랜덤함수를 호출해서 최하위 비트만 사용한다면.. 원래 랜덤함수의 짝/홀 비율에 따라 결과값이 달라지겠져.. 음.. -_-; 뭐 그런 식으로..

축구 잼나게 보세영 ㅎㅎ

Posted 19 Jun 2006 at 12:10 am
11. 민구 wrote:

“과연 후자가 더 좋은 random을 제공할까요??
이건 우리가 쓰는 random generator의 성능에 대한 문제제기이기도 하지만,
즉 그냥 random generator의 성능에 달렸다..라고 답하면 끝날지 모르겠지만..
후자가 더 좋을것만 같은 이 느낌은 뭔지-_-;;; ”

이 부분에 대해서는, abraxsus 네가 인용한 논문을 보면, 여러개의 히스토리를 보면서, 다수의 random generator 를 cobine하는것이 지금까지에서 최선의 기법이다.. 라고 나왔는데 그걸 생각한다면 여러번 던지는 게 좋을 것 같아보일 수도 있다.

그치만, 하나의 random number generator를 가지고 여러번 던지는 건 뭐 어차피 슈도 랜덤이면 별로 나아진다는 보장은 없어보인다. 여러개를 조합하는게 아니니까. 그보다는 최초에 1~N을 뽑는 rand. num. gen. 이 내부적으로 여러개의 rand. num. gen. 을 조합해서 만들어지는게 낫겠지.

“k에 비해 N이 엄청 큰 경우라면, 새 자리에 들어갈 수 있는 숫자의 목록 대신 들어갈 수 없는 숫자의 목록을 저장해서 O(k^2) 시간에 답을 구할 수 있겠네요. ㅎㅎ”

이런 의미에서 abraxsus 군이 말한 처음의 방법(위 글에는 안나와있음)도 괜찮은듯. 방법은 1~N까지의 숫자를 갖는 셋을 만듭니다. rand. num. 을 생성한뒤 그 값을 인덱스로 갖는 숫자를 출력하고 set에서 제외합니다. 또 새로 rand. num.을 뽑는다. 다음 그 값을 인덱스로 갖는 숫자를 출력하고 set에서 제외합니다. 이를 반복한다입니다.

실제로 set은 설명을 위한 개념이므로, N이 크다면 space overhead 매우 작게 유지하면서 O(k^2)안에 답을 구할 수 있죠.. 특히 k가 작다고 가정한다면 이것도 나이스한 듯.

Posted 19 Jun 2006 at 2:05 am
12. 민구 wrote:

cobine -> combine, 로긴하기 귀찮군;;

Posted 19 Jun 2006 at 2:06 am
13. abraxsus wrote:

1.
아..그런 생각이셨군요..
제 원래 생각을 기어코 코딩해넣고말았읍니다-_-; 지저분하지만..
b = (int *)malloc(sizeof(int)*r);

for(i=0;i=j+1;k–) b[k]=b[k-1];
b[j] = rn+1;
printf(“%d “, b[j]);
}
소스보다는 예를 들어보자면,
10개중에 4개를 선택한다면, 먼저 1~10중에 하나를 고르는데 3이라하면
b[0]=3 을넣습니다. 두번째에는 1~9중에 하나를 고르는데 이게 4라고하면
먼저 b배열을 스캔하면서 4보다 같거나 작은게 발견될때마다 4를 1씩 증가시킵니다.
그러다가 큰것이 발견되면 그 지점에 삽입해넣습니다.
이제 b[1]=5가 됩니다. 즉 5가 선택된거죠.
다음엔 1~8중에 하나를 고르는데 4라고하면,
b[0]보다 크니까 5가 되고, b[1]과 같으니까 6이 되어서 b[2]=6이 됩니다.
6이 선택된거죠
마지막으로 1~7중에 하나를 고르는데 1이면 b[0]이 더크므로 b[0]앞에 삽입해넣습니다.
위에선 귀찮아서 배열로 처리햇는데 b배열을 리스트로 처리한다면
이 알고리즘은 k^2라 할수있겠죠..
이 과정에서 값들을 출력하면 permutation을 구하는거고
덤으로 b배열은 소팅된상태가 됩니다.-_-;;
k번의 random함수 호출만 하면 되죠..
구지 N이 무지클필요는 없읍니다..k와 N이 같아도 잘 동작하니까요..
time은 O(k^2)라볼수있고 메모리는 O(k)먹죠..
shuffle이 둘다 O(n), O(n)인것과 비교되네요..
shuffle.. 정말 간단하고 명쾌하고.. 훌륭한 알고리즘이네요..ㅠㅠ

2.
이것도 직접 코딩해넣었는데
nCr 에 대해서 combination값을 구하는게 O(r)이고, 전체 알고리즘은 O(n)에
동작하기에 O(nr)이라고 생각되네요. 머 어딘가 더 훌륭한 알고리즘이 있는지는
모르겠읍니당..ㅠㅠ; 소스는 보여드리기 민망할정도로 지저분해서…컹….

3. 에구..이건 굳이 답변을 바란건 아니었지만,…얘기해보자면,
TAOCP에서…permutation의 index를 통해서 구하는 방법이
언급되면서 하는말이, 작은 값에 대해서는 좋은 방법이지만, 좀만 커져도 범위가
n!로 커지기때문에 이런 큰 범위에 대해서 random generator를 돌린다는게 안좋다는.
그런 얘기였읍니다. generator의 accuracy가 떨어진다네요..그래서,
작은 범위의 숫자를 여러개 만들어서 그걸 합쳐서 index를 만든다는거죠..
(이건 permutation과 factorial number system의 관계에 의해서 성립하는 관계..)

여기서 궁금증이 생긴게, 정말 무지막지하게 큰 범위에 대해서 우리의 pseudo random generator
를 돌린다면, 이게, 공식에 의해 나오는거라, 적당한 범위에 대해서는 uniform하게 나오지만
범위가 너무 커서 랜덤성이 깨질수도 있겠다는거죠.. 가능한 얘기같지 않나요? ㅎㅎ..
정말 무지막지하게 큰 범위에서 랜덤을 뽑겠다면, 이런점이 충분히 우려된다고 보고,
저같아도 좋은 랜덤성을 보이는 작은 범위의 랜덤을 많이 뽑은뒤에 이걸
잘 붙여서(concatenation같은…) 값을 만드는 방식을 선택할것 같네요..
그냥 그런 생각을 *혼자*해봤읍니다.. 물론 저 역시 pseudo random generator의 질을
평가하는것에 대해서는 아는바 없죠.
만약 정말 완벽한 random generator가 있다면야 쓸데없는 생각이 되겠지만요..흠..

To 민구

아..그런게 있남? 다수의 ran.gen.을 합치는게 최선이라는 내용이??
내가 머 논문을 읽진 않았으니까-_-;;
여러번 던지기가 ran.gen.을 좋게하지 않을까 하는 추측을 해보는 이유는,
단일의 ran.gen.이 기껏 수학공식에 의거해서 동작하기때문이고, 이 공식이라는것들이
아무리 최선을 다했다고 해도 상당한 assumption들에 기반하고, 이정도면 충분하다..
라는 것들에 기반하기에, 범위가 커지면서 이런 약점들이 노출될수도 있을것이라는 심증인거고,
그렇다면 단일의 ran.gen.이 최선의 랜덤성을 보이는 범위가 있을것이고, 그렇다면,
이것들을 반복하는것이 랜덤성을 강화시켜줄수도 있겠거니.. 라고 생각하는것이지.
(단일 ran.gen.의 정의의 문제는 논외로하자..ㅎㅎ..
그냥 공식으로 뽑혀나오는게 단일 ran.gen.이라고 생각하자..)

Posted 19 Jun 2006 at 2:54 am
14. abraxsus wrote:

음냐~ 위의 코드가 깨지는군요..
생각좀 더해봤는데, shuffle도 k개만을 골라낸다면 time이 O(k)가 되겟네요
제 알고리즘은 개선의 여지는 찔끔~~있기는 하지만, GG입니다..
뭐 n이 무지막지 커서 shuffle의 space O(n)이 부담스러운 지경에야 좀 쓸만하겟죠..ㅠㅠ;
space의 부담을 time으로 옮겨놓은 꼴입니다..
여러가지 알고리즘을 다 종합해서 생각해볼때 포인트는 k번만큼 ran.gen.을 실행하되
범위를 하나씩 줄여나간다는것이죠..즉 하나씩 제끼면서 나머지중에서 뽑아낸다는거..
이건 다들 공통적이네요.. permutation index방식에도.
(사실 permutation index방식은 생각해보면 제꺼랑 동등합니다만…흠…)
결국 shuffling이 짱!! 이란 거죠.. 흘..
이 알고리즘의 훌륭한 부분은,.. 결국 swap을 통해서 이미 뽑힌것들과 뽑혀야할것들을
기가막히게 간단하게 분류하고 있다는거죠..
제꺼에서는 결국 이 부담이 k^2로 나타난것이고요.. 그로 인한 benefit인 space는..
미미했다는… 가슴아픈 현실…ㅠㅠ;;
GG… 여기까지..ㅠㅠ..
프랑스나 이겨라..컹~~

Posted 19 Jun 2006 at 3:17 am
15. abraxsus wrote:

JM님은 혹시 황의권이라고 아세요?? -_-;;
같은 사람일라나… 혹시나 해서요..ㅎㅎ

Posted 19 Jun 2006 at 4:16 am
16. JM wrote:

1.
예, 제가 생각했던 것이랑 비슷하네요. ^^;

2.
combination 구하는 것이야, 한번 구한 다음엔 lookup table 에 저장해 두면 되니까 amortized analysis 해 줘도 되고.. 그냥 상수시간으로 해도 괜찮지 않나 싶습니다. ㅎㅎ
저도 간단하게 작성해 보았는데, 기본적인 아이디어는 다르지 않을듯 싶습니다. p = 1부터 n까지 스캔해가면서, 현재 위치에 p를 넣는 경우 combination 의 개수가 현재 index 를 초과하는지를 보는 거죠.
index 를 ‘자신의 앞에 올 combination 의 갯수’ 라고 생각하면 명료해지는것 같네요. 그러므로 최대 O(n)?

// index is zero-based
vector getCombByIndex(int n, int r, long long index)
{
assert(index < c[n][r]); vector retVal;
// invariant:
// r = number of remaining positions
// retVal.back() < p for(int p = 1; p <= n && r > 0; ++p)
{
// c[n-p][r-1] is the number of combinations, having p at this position
if(c[n-p][r-1] <= index) index -= c[n-p][r-1]; else { retVal.pb(p); ----r; } } return retVal; } [/code] 3. 확실히 그건 generating function 의 종류에 따라 달라질 것 같다는 생각이 드네요.. ^^;; 4. 의권이형이요? 알죠~ :) 동일인은 아니고요...-_-;;;

Posted 19 Jun 2006 at 11:53 am
17. abraxsus wrote:

뒤늦게 ran. num. gen.에 대한 이야기 하나…
리눅 커널에선 pseudo ran. fun을 안쓰고 여러 environmental noise들..
키보드 타이핑, 인터럽트 타이밍, 등으로 entrophy pool을 유지하고 여기서
ran. num.을 제공하는데, 잘 만들었다고 생각되는게, 이런 noise를 수집해서
이 entrophy pool의 entrophy를 항상 일정수준 이상이 되도록 유지한다는거.
entrophy estimate를 해서 유지하는데 이게 0에 다다르면 심지어 ran. num.을 생성해 주지도
않는다. 더구나 이 entrophy pool자체에는 절대 접근할수 없고 우리가 구하는 num들은
이것의 SHA값이라는거지. pseudo ran. fun을 쓰는것보다 이게 더 true random이라고 할수 있지 않을까.. 하는 생각이 드네.. 이 책에서는 true random number라고 자신있게 써놨는데..흠..
또 심지어 부팅시의 일정한 패턴을 피하기 위해서 대부분의 리눅스에서는 shutdown시에 entrophy pool을 저장해놓고 재부팅시엔 load해서 쓰게 된다…
역시 잘 만들었다는 생각이 든다..
이 entrophy개념은 Shannon entrophy라고 불리는데, 새넌이 randomness에 대한 용어를
찾고있는데 옆에 있던 친구인 -_-; 폰노이만이 엔트로피어때? 이렇게 해서 도입된 용어라나 머라나..-_-; 암튼 이 entrophy는 심볼당 bit의 수로 측정된다는데.. 좀더 조사해봐야-_-;;
섀넌 아저씨 참 대단하지.. security쪽에도 기반을 닦았으니. public key기법이전의 DES같은
전통적인 symmetric key방식은 정확히 섀넌 아저씨의 Feitel구조(맞나..용어가..)의 구현이거든.
암튼 요즘 interest가 security쪽으로 이동중이다..
별로 이야기를 풀어놓을데가 없어서 여기다 남긴다.. 근데 블로그가 원래 이런거냐..
이 article을 찾아헤맸잖아-_-;;

Posted 17 Jul 2006 at 4:43 pm
18. abraxsus wrote:

그나마 쉬운 소개인듯..

http://www.bearcave.com/misl/misl_tech/wavelets/compression/shannon.html

심오한 개념이구나. Shannon entropy.. 압축과 연관성이 깊다. 압축의 lower bound를 제공한다는데… 기본적인 lower bound인듯.
압축과 random도 연관성이 많지…
어렵다..흘…

Posted 17 Jul 2006 at 5:00 pm
19. MKSeo wrote:

블로그 우측에 검색창있잖아. 거기 random넣으면 나와 ㅎㅎ

Posted 18 Jul 2006 at 2:19 am
20. MKSeo wrote:

음, 엔트로피를 일정하게 유지한다는 것은 아마도 다음에 나올 수 있는 숫자가 1~n 이라고 할때 이 숫자가 각각 나올 확률을 1/n 으로 유지한다는 것 밖에 안되는 것 같은데. 뭐가 random한가 아닌가를 이야기할때는 흔히 uniform distribution을 이야기하겠지만서도 ‘1,2,3,4,…,n’의 시퀀스도 uniform distribution이지만 random하다고 아무도 동의하지는 않을 것 같다. 그런 의미에서 (아직 읽어보진 않았지만) taocp 에 나오는 스펙트럼을 사용한 분석이 설득력을 얻는 듯. 뭐 네가 무슨 책을 말하는지 모르고 안읽어봐서 어떻게 그책에선 그렇게 자신있게 말하는진 모르겠지만;; 음, 그리고 언제 안내려오나? ㅎㅎ

Posted 18 Jul 2006 at 2:32 am

Your email is never published nor shared.