random (1)

랜덤(random)한 수를 다루는 문제는 수학적 코딩 문제의 대표적 유형으로서 자주 출제되나 이 문제를 해결하려면 결코 녹록지가 않다. 이산수학, 조합수학, 추상대수 등의 개념을 담고 있기 때문이다. 하지만 그런 어려운 수학을 전부 공부하지 않더라도 직관과 상식으로 이를 풀어낼 수 있고, 대표적 문제들을 풀다보면 변형된 형태에도 대응할 수 있을 것이라 믿는다. 이 번 포스트에서는 몇 가지 연관된 문제를 풀어본다. EPI (Elements of Programming Interviews in Python)과 LeetCode 등을 참고했다.

부분집합 1

문제: 서로 다른 숫자로 된 배열(원소 n개) A에서 정해진 크기(k)만큼의 원소를 갖는 부분집합 1개를 찾기. 각 부분집합이 나타날 확률은 동일해야 한다. 원래 주어진 집합의 앞부터 k개만큼을 답이 될 원소로 채울 것(in-place).

해설: 크기가 k인 부분집합을 모두 뽑아 한 개를 랜덤으로 뽑으면 될까. 우선 이 방법 자체가 보기보다 상당히 어려운 문제이고 시간도 많이 걸린다. 나중에 따로 다루겠다.

그러면 이 문제를 부분으로 쪼개보자. 우선 원소가 k개인 부분집합을 구하려면 (말장난같지만) k-1개인 부분집합을 구한 다음에 1개를 랜덤으로 골라 추가하면 된다. 그렇다면 이 과정은 base case인 1개짜리 부분집합으로부터 목표한 k 만큼의 원소 수가 될 때 까지 작업하면 된다.

구체적으로, k = 1일 때는 RNG (random number generator) 를 불러와서, 필요한 경우 mod n을 하여 원소 n개 짜리 배열(A라고 하자) 중에 한 개 원소를 고른다. 이것을 r 번째였다고 하자 (0 <= r < n). 그러면 우리는 in-place로 돌려줘야 하니까,

swap(A[0], A[r])

을 해야 한다. 그리고 이미 k 개 중에서 0번째는 해결했으니, 다음 자리에 채울 것을 배열의 나머지 원소인 A[1, n-1] 중에 뽑는다. 위에서 이미 swap을 했기 때문에 원래 A[0] 자리에 있던 것은 A[r] 자리에 가 버렸다. 우리가 지금 신경쓸 것은 그저 A의 index 1부터 n-1까지 중에서 하나를 뽑아 A[1] 자리로 보낸다는 것이다 (혹시 헷갈릴 수 있어 언급하면 A[1] 자리에 있던 것이 뽑혀서 그대로 A[1] 자리로 가는 경우도 있다. 실제 스왑은 일어나지 않겠지만 이 경우를 따로 고려할 필요없이 위 로직에 포함된다).

def random_sample(k, A):
    for i in range(k):   # 0:k-1, thus do k times
        # we pick random numbers among 0:n-1, 1:n-1, ... , k-1:n-1, thus i:n-1
        r = random.randint(i, len(A) - 1)   # inclusive
        A[i], A[r] = A[r], A[i]             # swap

random 함수는 알아두면 편하게 쓸 수 있다. 이 외에도 다음 함수를 참고할 만 하다.

import random

random.randrange(15)   # same as range [0, 15)
random.randint(3,15)   # inclusive [3, 15]
random.random()        # don't need to mention argument, as it returns between (0, 1)
random.shuffle(A)      # shuffle list A randomly
random.choice(A)       # pick one of elements in A randomly

순열

문제: 랜덤한 순열을 만들어라.

해설: 결론부터 말하면 위의 함수를 활용할 수 있다. 즉, n개 원소 중에서 n개를 포함한 subset을 만들때, 그 subset의 각 원소들을 매번 랜덤하게 뽑기 때문에 이것은 랜덤한 순열이라고 할 수 있다. 순열이란 정해진 숫자들을 다른 순서로 나열한 것에 다름 아니기 때문이다.

def random_perm(n):
    perm = list(range(n))
    random_sample(n, perm)
    return perm

부분집합 2

문제: 이번에는 부분집합 크기 k와 함께, 패킷을 계속 입력받아 역시 일양 랜덤 부분집합(uniform random subset)을 유지하는 것이 문제이다.

해설: 예를 들어, k = 2 라고 하고, 패킷이 pqrtuv 순서로 읽힌다면, 일단 앞의 두개를 부분집합에 포함한다: {p, q}. 그 다음 패킷을 선택하려면 총 입수한 패킷의 수인 3개 중에 2개를 선택해야 하므로 2/3의 확률로 p, q, r 중에 2개를 선택한다. 만약에 r이 선택되었다면, 이제 총 부분집합 원소 수를 k = 2개로 유지해야 하므로, 기존의 {p, q} 중에 하나를 선택해 바꿔야 하며, 이 확률은 늘 1/2이 된다.

def online_random_sample(it, k):
    sample = list(itertools.islice(it, k))    # read k iterator
    read = k       # how many iterators have I read from stream
    for p in it:   # read one more packet from iterator
    	read += 1  # augment counter of how many I read
        replace_id = random.randrange(read)   # 0:read-1
        if replace_id < k:   # if randomly selected id to be replaced were within previous subset
            sample[replace_id] = p  # replace it with newly read packet
    return sample  # kept doin' that for whole iterator stream, now ready to return.