생각보다 자주 맞이하게 되는 간단한 문제.
random shuffling.

많이 알려진바와 같이, 간단한 구현이지만 작지않은 함정이 존재한다.
-얼마전까진, 간과해왔던...-

1,2,...,n 의 sequence를 random shuffle 한다는 것은,
결과의 sequence a1,a2,...,an의 각 위치에 대한 확률이 모두 1/n으로 결정되는 것.

아무생각없이 아래와 같은 코드를 작성하곤 했는데...

for(int i=0;i<n;i++)
    swap(a[i],a[random(n)]);

...
이녀석은, 1/n의 확률을 유지해주지 못한다......쩝.

for(int i=0;i<n;i++)
     swap(a[i],a[random(n-i)]);

이녀석은, 1/n의 확률이 유지된다...
-간단한 문제니 pass..모른다면, 확률 공부를 하시길...

요는,
아무리 간단한 문제라도 문제의 요구사항을 명확히 하고 그것을 만족하는 결과를
만들어내고 있는가를 검증하는 것을 소홀히해서는 안된다는 것.

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.