중복하지 않는 난수 발생 기법 Part 3-Shuffling

이전 포스팅에선 C#과 파이썬에서 random 클래스 사용과 고려해야 할 점에 대해 살펴봤다. 이번에는 셔플링(shuffling; 카드섞기) 기법에 대해 다루도록 한다.

Contents
1. Array in C# and List in Python
2. random in C# and Python
3. Shuffling
4. Shuffling in Python
5. Lottery

 

3. Shuffling

셔플링 혹은 카드섞기 기법은 다음과 같은 절차를 거친다.

1) 뽑기 원하는 항목으로 채운 배열 혹은 리스트를 준비한다.

2) 배열 또는 리스트 인덱스 범위에 드는 두 난수를 얻는다.

3) 두 인덱스에 해당하는 요소를 교환한다.

4) 위 2), 3) 과정을 지정된 회수만큼 반복한다.

 

위 과정을 그림으로 설명하겠다. 1에서 6까지 6장의 카드가 있고, 흰색과 검은색 주사위가 아래 그림과 같이 있다고 하자. 흰색과 검은색 두 주사위를 각각 굴려 나온 숫자 위치에 있는 카드를 서로 교환한다. (물론 두 주사위를 굴리는 것은 독립실행이다.)

두 주사위를 굴렸더니 각각 3과 1이 나왔다. 그래서 첫 번째 위치에 있는 카드와 세 번째 위치에 있는 카드를 뽑아 자리를 교체했다.

다시 두 주사위를 굴렸더니 이번에는 각각 4와 2가 나왔다. 앞에서 시행한 바와 같이 두 카드 자리를 교체했다.

마지막으로 두 주사위를 굴렸더니 이번에는 두 주사위 모두 1이 나왔다. 첫 번째 카드를 뽑았다 다시 넣었다. (혹은 첫 번째 자리에 카드를 첫 번째 카드 자리와 교체 했다.)

위 과정을 시행 후 3장의 카드를 맨 위에서 차례로 꺼내면, 원래 1, 2, 3이었던 카드가 3, 4, 1 (혹은 정렬을 시행하면 1, 3, 4) 가 된다. 이를 카드 섞기 기법이라 한다.

C# 코드로 이를 작성하자면 우선 1부터 45까지 든 배열과 난수 발생을 위한 Random 클래스의 인스턴스가 필요로 하다.

아래 그림과 같이 private scope을 가지도록 int 형 배열과 Random 클래스 인스턴스를 선언했다.

난수 발생 메소드는 배열 인덱스에 맞춰, 0에서 44 범위에서 int 형 난수 하나를 얻도록 했고(Random 클래스의 Next(min, max) 메소드로 얻는 난수 N은 min ≤ N < max 범위를 가지는 임의의 정수이다.) 배열 요소간 교환(swap) 메소드는 다음과 같이 작성했다. (이 포스팅에서 작성한 C# 코드는 Console App. 이므로 private scope 변수 및 메소드를 static으로 선언했다.)

이후 프로그램 시작 지점 void Main(string[] args)에서 루프를 시행 후 인덱스 0에서 5까지 6개 숫자를 추출하면 된다. 여기서는 보너스 번호가 6번째 숫자임을 감안하고 첫 5개 숫자를 정렬해 결과를 보여주도록 했다.

실행 결과는 다음과 같다.

파이썬에서는 random 클래스에서 제공하는 메소드만으로 위와 같은 카드 섞기 기법을 이용할 수 있지만 이 포스팅에선 우선 위 C# 코드와 같은 방식으로 코드를 작성하겠다.

random 클래스를 불러오고, 1부터 45까지 연속된 정수를 포함한 리스트를 하나 생성 했다.

난수 발생 메소드(rollDice)와 배열 요소 교환 메소드(swapDeck)은 아래와 같이 작성했다. 파이썬의 경우 기존 프로그래밍 언어와 달리 메소드 결과를 1개 이상 복수로 리턴 할 수 있다. rollDice() 메소드에서 return 구문 다음에 두 개 리턴 값을 돌려주며 이를 받기 위해선 a, b = rollDice() 형태로 받아주면 된다.

100회 루프를 시행 후 얻은 결과를 얻는 코드를 아래에 나타내었다. 파이썬의 리스트에서 list[:6] 으로 콜론 후 숫자는 리턴 할 인자 개수를 의미한다. 예를 들어 인덱스 1에서 시작해서 10개 값을 얻고자 하면 list[1:10] 이라하면 인덱스 1부터 10까지 10개 값을 리턴한다.

아래 코드에서 result = lottoDeck[:5]는 lottoDeck 리스트의 인덱스 0부터 시작하는 5개 요소 값을 result에 할당 하란 뜻이다. 이를 list.sort() 메소드를 통해 소팅 후 result 리스트와 lottoDeck[5] 값을 쉘에서 나타내도록 했다.(파이썬 쉘에서는 변수 명을 기입하면 값이 표시된다.)

혹은 result.append(lottoDeck[5]) 를 해서 result 리스트에 lottoDeck[5] 값을 추가 할 수도 있다.

다음 포스트에선 카드 섞기 기법을 파이썬 random 클래스가 제공하는 메소드로 더 쉽게 접근토록 한다.

중복하지 않는 난수 발생 기법 Part 2-random in C# and Python

이전 포스팅에선 C#과 Python에서 데이터 그룹을 이용하기 위해 배열(Array)와 리스트(List)를 사용하는 방법에 대해 살펴봤다. 이번 포스팅에선 난수 발생을 위한 random 사용과 고려해야 할 점을 다루도록 한다.

 

Contents
1. Array in C# and List in Python
2. random in C# and Python
3. Shuffling
4. Shuffling in Python
5. Lottery

 

2. random in C# and Python

C#은 난수 발생기로 Random 클래스를 제공한다. 네임스페이스 System에 속한 클래스이므로 별도의 네임스페이스 선언을 하지 않아도 된다.

2005년 10월 19일자에 네이버 블로그에 포스팅했던 C#에서의 Shuffling 기법에서 Random 클래스 사용시 발생한 문제와 그 해결을 자세히 다루었기 때문에 결론만 말하자면 “프로그램 내에서 Random 클래스의 인스턴스는 단 한번만 생성하고 이를 계속 사용토록 하라”는 것이다.

0부터 100사이 난수를 발생하는 코드 작성을 아래 두 가지 방법으로 비교해보자.

Case 1 : 메소드 호출을 통한 경우 – 인스턴스 반복 생성

위 코드에선 randomPick() 메소드 호출 시마다 Random 클래스의 새로운 인스턴스가 생성된다.

코드 실행 결과를 보면 다음과 유사하게 된다.

Case 2 : 인스턴스를 한번 생성 후 반복 호출을 통한 경우

위 코드는 Random 클래스 인스턴스를 한번 생성 후 해당 인스턴스를 통해 난수를 반복해서 얻는다.

코드 실행 결과를 보면 다음과 유사하게 된다.

두 실행 결과간 차이를 알아보기 힘들다면 아래와 같은 코드와 그 실행 결과를 살펴보자. 아래 코드는 두 방법으로 각각 생성한 난수를 제너릭(generic) 리스트 클래스의 인스턴스에 넣은 후 생성된 난수의 개수를 구하여 콘솔에 출력하는 것이다. 생성된 난수 개수를 구하는 것은 Linq를 이용하였다. private 영역에서 생성한 Random 클래스의 인스턴스(rand1)의 경우는 seed를 제외했는데 seed를 주더라도 유사한 결과를 얻게 된다. 매번 새롭게 인스턴스가 생성되는 rand2 경우 seed를 제외하면 매우 나쁜 결과를 얻게 된다.

위 코드를 실행하면, 생성된 난수 목록을 세미콜론(;)으로 구분하여 보여준 후, 난수 개수를 내림차순으로 보여준다.

이런 현상이 발생하는 원인은 명확하다. 메소드 호출로 Random 클래스 인스턴스 생성 시 할당하는 seed가 나쁘기 때문이다. Random 클래스를 이용 시, 많은 이들이 seed로 ticks를 습관적으로 사용하는데, patch time이 짧은 상태에서 사용하는 것 자체가 문제를 일으킨다. 아래 코드로 이를 확인해보자.

위 코드는 10회 동안 ticks를 호출하여, 원래 리턴 타입인 long 타입 값과 이를 int 타입으로 변환(casting) 한 값을 콘솔로 출력하는 것이다.

즉 메소드 호출 patch 타임이 ticks 값 변화를 선행하기 때문에 발생하는 문제라 할 수 있다. 이를 해결 하는 방법으로 다음과 같이 코드를 수정 할 수 있다. 다만 이렇게 인스턴스를 반복해서 생성하는 것 보다는 인스턴스를 한번 생성 후 난수를 반복해서 생성하는 것이 여러모로 좋다.

C#의 Random 클래스에서 Next() 메소드는 int 타입의 정수를 리턴 한다. Next() 메소드는 Next(), Next(int maxValue), Next(int minValue, int maxValue) 3개 메소드가 오버로딩 되어 있으며, 주의 할 점은 minValue는 포함이나, maxValue는 제외, 즉 Next(n) 일 경우엔 0 ≤ x < n 이고, Next(m, n) 일 경우엔 m ≤ x < n 의 결과를 얻는다. 0과 0.1 사이 double 타입 실수 값을 얻고자 한다면 NextDouble() 메소드를 사용한다.

파이썬에서 random을 이용하기 위해선 random 모듈 불러오기(import)를 먼저 해야 한다. 난수 발생 함수는 C#에서와 마찬가지로 정수형 데이터나 실수형 데이터를 되돌려 주는데 그 종류는 C#에 비해 매우 다양하다. 예를 들어, 정규분포에서 난수 값을 돌려주는 random.normalvariate(mu, sigma)나 가우스 분포에서 되돌려주는 random.gauss(mu, sigma) 지수 분포나 베타 분포 등도 구비되어 있다. 여기서는 기본 함수 중 0과 1 사이 실수 형 난수를 되돌려주는 random.random(), 지정된 값 사이(최대 값 포함) random.uniform(a, b), 연속하는 정수 범위 중 난수를 되돌려주는(최대 값 포함하는) random.randint(a, b)과 일정한 증가 값을 가지는 정수 범위 중 난수를 되돌려주는(최대 값 제외) random.randrange([start], stop, [, step])만 살펴보겠다. 참고로 파이썬 또한 random 모듈 호출 시 seed 값을 주지 않으면 시스템 시간을 seed로 이용한다.

아래 코드는 random.random() 함수를 이용해 50회 반복 시행한 것이다. print() 문의 종료는 기본 값인 줄 바꿈 대신 세미 콜론(;)으로 대신하였다.

발생 한 난수 개수를 얻기 위해 itertool 모듈을 함께 불러와서 리스트 클래스의 빈 인스턴스를 하나 생성 후 리스트에 50개 난수를 넣고 그 개수를 계산했다. 첫 번째 개수 구하는 코드는 [생성된 값, 개수] 리스트로 생성했고, 두 번째 코드는 개수만 다시 리턴토록 했다. itertools.groupby(sorted(li))로 인해 발생 한 난수는 내림차순으로 정렬 된 상태로 출력된다.

다음 코드는 지정된 정수 범위 내 실수형 난수를 발생하는 random.uniform(a, b)로 주의 할 점은 발생하는 실수형 난수 N은 a ≤ N ≤ b 라는 점이다. 단, python documentation(v2.7.1 기준)에 따르면 b 값은 생성 될 수도 있고 아닐 수도 있는데 이는 a + (b – a) * random() 계산 후 소수부의 정수화(rounding) 결과에 따라 달라진다는 점을 주의해야 한다.

지정된 범위 내 정수형 난수를 생성하는 random.randint(a, b)의 경우도 정수형 난수 N은 a ≤ N ≤ b 사이에서 발생한다.

마지막으로 random.randrange([start], stop [, step])으로 발생하는 정수형 난수 N은 stop 에 지정한 값보다 작다. start 생략 시엔 0으로 고정된다. 또한 아래 코드에 생성된 난수 목록에 보이다 싶이, start와 stop 사이 연속하는 값이 아닌 stop 보다 작은 step 배수 값 중에 난수가 발생한다.

이번 포스트에선 C#과 python에서 random을 통해 난수 생성에 대해 살펴봤다. 다음 포스트에선 카드 섞기 혹은 셔플링(shuffling)이라 불리는 기법을 다루도록 한다.

중복하지 않는 난수 발생 기법 Part 1–Array in C# and List in Python

네이버 등을 검색해보면 로또 번호 생성기 소스가 많이 돌아다닌다. 랜덤을 이용해 번호 6개를 생성하는데 너나 할 것 없이 난수 발생 후 앞서 추출한 난수 목록에서 중복하는지 여부를 살펴보고 있으면 무시하고 없으면 추가하는 형태로 프로그램을 작성한다.

이를 보고 있으면 마치, “1부터 n까지 연속하는 자연수의 합을 구하라” 혹은 “m부터 n까지 연속하는 자연수의 합을 구하라”라고 물으면 어김없이 for (int i = 1; i < n + 1; i++) { result += i; } 라는 식으로 프로그램을 작성하는 것과 같은 난감함을 느낀다. 또는 DB 시퀄 쿼리 작성 시, 레코드 마다 어떤 작업을 처리해야 할 때 아무 생각 없이 cursor를 휘갈겨 쓰는 것과도 같다. (http://oscarsjpark.blogspot.com/2011/05/sql-query.html)

앞으로 총 5개 포스트를 통해 C#과 Python으로 로또 번호 추출 프로그램을 다룰 것이다. 이와 같은 중복하지 않는 난수 발생 기법은 보드 게임(화투, 포커 등) 또는 통계 처리를 위한 표본 선정 등에 동일하게 적용 할 수 있다.

 

Contents
1. Array in C# and List in Python
2. random in C# and Python
3. Shuffling
4. Shuffling in Python
5. Lottery

 

1. Array in C# and List

C#에서 배열 선언은 기존 C계열 언어에서와 그 용법은 동일하거나 유사하다. 로또의 경우 1부터 45까지 연속된 자연수 모음이므로 다음과 같이 선언할 수 있다.

// C#

static int[] lottoDeck = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
                                  16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
                                  28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
                                  40, 41, 42, 43, 44, 45};

static 키워드로 할당 했을 때와 하지 않았을 때 차이를 메모리 내 heap과 stack을 언급하며 설명 하는 것은 너무 멀리 나가니 이에 대해 궁금하다면 Effective C# 등과 같은 서적을 참고하면 된다.

파이썬 기본 데이터 타입은 Number, String 그리고 List만 제공한다. (물론 List를 prototype으로 삼아 Hash를 제공하고 있다. 또 indexing 되지 않는 set도 제공한다.) 파이썬의 List 용법은 LISP에서와 같으며, C# 또는 자바에선 ArrayList, List<> (generic) 등과 같다.

# Python

lottoDeck = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
                   16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
                   28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
                   40, 41, 42, 43, 44, 45]

Python에는 range 함수가 있어 아래와 같은 코드도 가능하다.

# Python

lottoDeck = range(1, 46)

IDLE 인터프리터에서 range를 이용한 것을 아래 그림에서 볼 수 있다. 단 range(min, max) 함수 호출 시, min 파라메터는 포함관계이고, max 파라메터는 제외관계이다.

흥미로운 것은 실제 모든 값을 나열하여 리스트를 생성한 것과 range로 만들었을 때 아래 그림과 같이 차이가 나는데 이는 python이 생성한 list 객체가 실제 데이터를 가질 수도 있지만 생성 규칙(production rule)을 가질 수도 있기 때문이다. 이는 근래 각광받는 언어학자인 Steve Pinker가 그의 저서 단어와 규칙에서 밝힌 바와 같이 인간의 마음 사전과 동일하다. 즉 영어에서 boy 가 boys 가 되고, work 가 worked 가 되는 것과 같은 규칙에 의해 변하는 단어는 암기 하지 않는다. 하지만 child 가 children 으로, calclus 가 calculi 로, run 이 ran 과 같이 불규칙하게 변하는 단어만 마음 사전에 담아두면 된다. (불규칙 단어는 약 120 ~ 170 여 개가 된다고 한다. 사실 이들 불규칙 단어도 핑커의 연구 결과에 따르면 음성학적인 규칙을 따르지만…)

값 할당으로 만든 리스트와 달리 생성 규칙에 의해 만들어진 리스트는 값 요청 시에 해당 값을 되돌려 주게 되므로 리스트 내 요소(element) 값을 변경 할 수 없다.

Python에서 리스트 내 요소간 교환(swap)을 하고자 한다면 값 할당을 통해 리스트를 생성해야만 한다.

다음 포스트에선 난수 생성을 위한 random을 활용하는 방법에 대해 살펴보도록 한다.