무작위 순열

무작위 순열(random permutation)은 특정 집합에 포함된 원소들의 순서를 무작위로 섞은 결과를 의미한다. 이는 통계적 샘플링, 시뮬레이션, 알고리즘 설계 등 다양한 분야에서 널리 사용되며, 특히 무작위성과 공정성을 확보하는 데 중요하다.

1 개념

n개의 서로 다른 원소로 이루어진 집합 S = {1, 2, ..., n}이 있을 때, 그 순서를 임의로 섞은 결과를 무작위 순열이라고 한다. 무작위 순열은 n!개의 가능한 순열 중 하나를 균등한 확률로 선택하는 것을 의미한다.

• 예: S = {1, 2, 3}
  • 가능한 순열의 수: 3! = 6
  • 무작위 순열 예시: {2, 1, 3}, {3, 1, 2}, ...

2 생성 방법

• Fisher–Yates 셔플 알고리즘 (Knuth shuffle)
  • 가장 널리 쓰이는 무작위 순열 생성 알고리즘
  • O(n) 시간 복잡도
  • 각 순열이 동일한 확률로 생성됨

절차:

1. 배열 A[1..n]이 주어짐
2. i = n부터 2까지 감소하면서 다음을 수행:
   • j를 1 이상 i 이하에서 무작위로 선택
   • A[i]와 A[j]를 교환

3 예시

• Python 예시
  • `random.shuffle(list)` → 리스트 자체를 무작위 순열로 섞음
  • `numpy.random.permutation(n)` → 0부터 n−1까지의 무작위 순열 생성

활용

• 부트스트랩과 재표본 추출
• 실험 설계에서 무작위 배정
• 퍼즐 생성, 카드 섞기 등
• 알고리즘 검증 및 테스트 케이스 생성

유의 사항

• 단순한 교환 반복은 편향된 순열을 만들 수 있음
  • 예: `for i in range(n): swap A[i] with A[random index]`는 잘못된 방식
• 반드시 균등 분포(uniform distribution)를 보장하는 알고리즘을 사용해야 함

같이 보기

• 순열
• 조합
• 확률
• 셔플 알고리즘
• 의사난수
• 부트스트랩 (통계)

참고 문헌

• Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. Addison-Wesley
• Durstenfeld, R. (1964). Algorithm 235: Random permutation. Communications of the ACM, 7(7), 420