셔플의 핵심은 “무작위로 섞어 보인다”가 아니라 각 순열에 같은 확률을 주는 것입니다. 알고리즘 자체는 한 주기의 순서를 만들고, 어떤 질문을 이미 보여 주었는지와 새 항목을 언제 포함할지는 별도의 덱 수명 정책입니다.
독립 추출과 주기 내 중복 없는 순회
질문 네 개에서 매 클릭마다 독립적으로 하나를 고르면 직전에 본 질문이 다시 나올 수 있습니다. 각 질문의 선택 확률이 같다는 점에서는 공정하지만, 한 바퀴 동안 모두 다른 질문을 보여 주겠다는 요구에는 맞지 않습니다.
배열 전체를 무작위 순열로 만든 뒤 하나씩 꺼내면 한 주기 안의 중복을 막을 수 있습니다. Fisher–Yates 셔플은 매번 남은 범위에서 균등한 위치를 골라 한 자리를 확정하는 방식입니다. 목록에 같은 값이 두 번 들어 있다면 두 발생 항목은 여전히 별개이므로, 질문 ID의 중복은 입력 단계에서 제거해야 합니다.
후방 위치의 단계별 확정
배열 [A,B,C,D]에서 뒤부터 진행합니다. 다음 난수 선택은 설명을 위한 한 경로입니다.
| 단계 | 선택 범위 | 선택 j | 교환 뒤 배열 | 확정된 뒤쪽 |
|---|---|---|---|---|
| i=3 | 0~3 | 1 | A,D,C,B | B |
| i=2 | 0~2 | 0 | C,D,A,B | A,B |
| i=1 | 0~1 | 1 | C,D,A,B | D,A,B |
i보다 뒤쪽은 더 이상 건드리지 않습니다. j=i도 정상적인 선택입니다. “반드시 다른 자리와 바꾼다”며 j=i를 제외하면 가능한 순열과 확률이 달라집니다.
그림을 글로 읽기
- A · B · C · D: 후보 4개
- A · D · C │ B: j=1, D와 B 교환
- C · D │ A · B: j=0, C와 A 교환
- C │ D · A · B: j=1, 자기 자리 선택
- A · B · C · D → A · D · C │ B: 마지막 자리 확정
- A · D · C │ B → C · D │ A · B: 다음 자리 확정
- C · D │ A · B → C │ D · A · B: 남은 둘 중 선택
모든 순열이 같은 확률인 이유
마지막 자리에 올 항목은 n개 중 하나이므로 확률 1/n입니다. 그다음 자리는 남은 n-1개 중 하나이고, 앞의 선택을 조건으로 확률 1/(n-1)입니다. 특정 완성 순열을 만드는 선택 경로는 하나이며 확률은 1/n!입니다. 각 단계의 균등한 범위 선택과 적절한 독립성이 전제입니다.
shuffle(a):
for i from length(a)-1 down to 1:
j = uniformBelow(i+1) # 0 <= j <= i
swap(a[i], a[j])
return a
시간은 O(n), 제자리 교환이면 보조 공간은 O(1)입니다.
재현 가능한 검사는 작은 입력에서 난수 선택 자체를 기록하는 방식이 가장 분명합니다. [A,B,C,D]에 대해 첫 선택이 j=1, 다음이 j=0, 마지막이 j=1이면 표의 C,D,A,B가 나오고, 같은 선택을 다시 주입하면 같은 결과가 나와야 합니다. 모든 단계에서 j=i를 허용하는 구현과 허용하지 않는 구현을 각각 비교하면 후자가 24개 순열을 동일하게 만들지 못하는 반례를 확인할 수 있습니다.
운영에서 새로고침 반복이 관찰되면 먼저 셔플 분포를 의심하기보다 remainingIds, 현재 인덱스, 주기 식별자의 저장·복원 시점을 로그로 남깁니다. 분포 검사는 n=4 전수 열거로 하고, 저장 복원·수동 이동·삭제는 별도의 상태 전이 시험으로 분리해야 원인이 알고리즘인지 지속성인지 빠르게 좁힐 수 있습니다. 원본 순서를 보존하려면 배열 복사 O(n)이 추가됩니다. 정렬 비교 함수에서 무작위 양수·음수를 반환하면 비교의 일관성 계약을 깨며, 정렬 구현에 따라 편향된 결과가 나옵니다. 무작위 비교는 셔플의 대체물이 아닙니다.
덱 상태와 셔플 알고리즘 외부의 지속성 계약
한 번 만든 덱에서 이미 본 질문을 제거하고 남은 ID를 저장하면 새로고침 후에도 반복을 줄일 수 있습니다. 배열만 저장하고 현재 위치를 잊으면 처음부터 다시 보여 줄 수 있습니다. 브라우저 저장소가 막히거나 비워질 때는 저장 실패 때문에 화면 자체가 멈추지 않도록 메모리 덱으로 계속하되, 주기 상태가 유지되지 않을 수 있음을 구분합니다.
| 사건 | 필요한 상태 처리 | 달라지는 보장 |
|---|---|---|
| 새로고침 | 남은 ID와 이미 방문한 범위 복원 | 저장이 유지되는 동안 주기 보존 |
| 질문 삭제 | 남은 덱에서 ID 제거 | 존재하지 않는 주소 방지 |
| 질문 추가 | 새 ID를 현재 덱 또는 다음 주기에 포함 | 어느 주기에 포함할지 정책 |
| 목록 밖 수동 이동 | 방문 ID를 남은 덱에서 제거 | 랜덤 이동과 실제 방문 일치 |
| 주기 종료 | 새 순열 생성 | 주기 사이 즉시 반복 여부 별도 |
서로 다른 탭·기기에서 공유된 방문 상태가 필요하다면 로컬 브라우저 저장만으로는 충분하지 않습니다. 또한 카테고리를 번갈아 보여 주거나 최근 질문을 제외하면 전체 균등 순열과는 다른 정책이 됩니다. 학습 효과를 위해 선택할 수 있지만 무작위 알고리즘의 원래 분포와 혼동하지 않습니다.
주기 경계 반복 회피와 조건부 편향
직전 질문이 X였다고 하겠습니다. 새 순열을 균등하게 만든 뒤 첫 항목이 X이면 그 순열 전체를 버리고 다시 만들면, 항목이 둘 이상일 때 “첫 항목이 X가 아님”이라는 조건부 분포를 유지할 수 있습니다. 다만 한 번에 통과한다는 보장은 없으므로 재시도 상한을 둔다면 상한에 도달했을 때 중단할지, 균등성을 따로 보장하는 다른 방법으로 전환할지 정해야 합니다. 바로 앞 질문을 후보에서 아예 제외해 새 주기를 시작하는 정책은 X의 이번 주기 노출 방식 자체를 바꾸므로 같은 셔플의 보장으로 설명하면 안 됩니다.
첫 항목과 항상 두 번째 항목을 바꾸는 방식은 반복은 줄일 수 있어도 허용된 순열 사이의 균등성까지 보장하지 않습니다. 항목이 하나뿐이면 어떤 방법으로도 즉시 반복을 피할 수 없으므로 버튼을 비활성화하거나 같은 항목을 유지하는 정책이 필요합니다.
순열 보존과 빈도 검사의 우선순위
빈 배열과 한 항목은 오류 없이 끝나야 합니다. 모든 단계에서 j=0, j=i를 주입해 범위를 확인하고, 결과의 ID 다중집합이 입력과 같으며 각 ID가 한 번만 등장하는지 검사합니다.
n=4에서는 선택 경로가 4×3×2=24개이므로 모두 열거해 24개 순열이 각각 한 번 나오는지 확인할 수 있습니다. 이후 저장 복원·추가·삭제·주기 전환은 별도 테스트로 다룹니다. 균등 셔플이 맞아도 덱 상태 관리가 틀리면 사용자에게는 같은 질문이 반복됩니다.