대칭 중복 없애기(정규형)와 이력 패널티를 준 가중치 랜덤 선택
패턴 목록을 자동으로 늘리고, 그중에서 '다양하게' 고르는 문제를 두 단계로 나눠 정리한다. 예시는 4키 리듬게임의 레인 패턴이다. 0~3은 레인, 패턴은 반복해서 도는 레인 배열이다(계단 = [0, 1, 2, 3]).
1. 변형으로 어휘 늘리기
패턴 하나에서 쉽게 새 모양을 만들 수 있다.
- 좌우 반전: 각 레인 l → 3 − l. [0, 1, 2, 3] → [3, 2, 1, 0]
- 역방향: 배열을 뒤집기
- 반전 + 역방향
문제는 이렇게 만들면 같은 모양이 여러 이름으로 생긴다는 것이다. 계단을 반전한 것과 역방향으로 한 것은 둘 다 [3, 2, 1, 0]이다. 게다가 패턴은 계속 도는 배열이라 [0, 3, 1, 2]와 [1, 2, 0, 3]은 시작 위치만 다른 같은 바퀴다.
2. 정규형(canonical form)으로 중복 판정
같은 것끼리는 같은 대표값으로 바뀌는 함수를 만들면, 대표값만 비교해서 중복을 없앨 수 있다. 회전에 대해서는 '가능한 모든 회전 중 사전순으로 가장 작은 것'을 대표로 쓴다.
길이 n이면 O(n²)이지만 패턴은 8칸 이하라 충분하다. 긴 문자열이면 최소 회전을 O(n)에 구하는 Booth 알고리즘이나 Lyndon 분해를 쓴다. 반전·역방향까지 '같은 것'으로 볼지는 목적에 따라 다르다. 여기선 반전·역방향은 다른 패턴으로 남기되(손 느낌이 다르니까) '변주 관계'로 묶어서 다양성 계산에 썼다.
3. 가중치 랜덤 선택
후보마다 가중치 wi가 있을 때 wi / Σw 확률로 하나를 뽑는다. 0~Σw 사이 난수 r을 뽑고, 앞에서부터 가중치를 빼다가 0 이하가 되는 후보를 고른다.
한 번 뽑을 때 O(n)이다. 같은 분포에서 아주 많이 뽑아야 하면 누적합 + 이분 탐색(O(log n))이나 alias method(O(1))를 쓰지만, 매번 가중치가 바뀌는 경우엔 이 방식이 제일 단순하다.
4. 이력 패널티로 다양성 만들기
그냥 뽑으면 가중치가 큰 후보가 계속 나온다. 이미 쓴 것을 기억해서 가중치를 깎는다.
- 누적 패널티: 곡 전체에서 n번 쓴 모양은 w / (1 + αn). 많이 쓸수록 점점 덜 나오지만 완전히 막지는 않는다.
- 최근 금지에 가까운 패널티: 최근 k번 안에 나온 모양은 × 작은 수(예: 0.12). 탐색 알고리즘의 tabu list를 부드럽게 만든 것과 같다. 완전 금지(0)로 하면 후보가 적을 때 막힌다.
- 계열 패널티: 모양은 달라도 같은 계열이 연달아 나오면 비슷하게 느껴지니 따로 깎는다.
같은 입력에서 늘 같은 결과(같은 곡이면 같은 채보)를 내야 하면 Math.random 대신 시드가 있는 난수를 쓴다. 간단한 선형 합동 생성기로 충분하다.
정리
- 변형으로 어휘를 늘릴 땐 정규형으로 중복부터 없앤다. 회전 대칭은 '최소 회전'이 대표값.
- 가중치 뽑기는 누적 빼기로 O(n), 반복이 많으면 누적합+이분 탐색이나 alias method.
- 다양성은 후보 수보다 '이미 쓴 것을 기억하는 패널티'에서 나온다. 완전 금지보다 부드러운 패널티가 막히지 않는다.
- 재현성이 필요하면 시드 있는 난수.