정수 파티션의 컨쥬 게이트

Question

n의 모든 파티션 세트에서 무작위로 선택된 정수 파티션의 컨쥬 게이트는 균일 한 무작위 샘플입니까? 내 결과는 그렇다. 길이가 긴 n의 임의의 파티션을 빠르게 생성하기 위해 고무되었지만, 왜 그렇게해야하는지 또는 그렇게해서는 안되는지 설명 할 수 없다.

내 결과는 1. 특정 길이의 작은 n (< 70)에 대한 모든 파티션을 생성합니다. 2. 각 파티션의 분산을 매크로 상태 설명자로 계산하고 3.) 전체 실현 가능 세트 (길이 n의 모든 파티션)에 대한 분산의 커널 밀도 곡선을 작은 무작위 샘플 (즉, 길이가 s 또는 공액 길이가 s와 일치하는 n의 임의로 생성 된 파티션 500 개)와 비교합니다. 무작위 샘플에 대한 커널 밀도 곡선은 실행 가능한 전체 집합 (즉, n 개의 일치하는 모든 부분)에 대한 곡선과 매우 일치합니다. 이는 대다수가 켤레 분할 인 무작위 표본이 n 및 s 기반 실현 가능한 집합의 분할간에 분산 분포를 포착한다는 것을 시각적으로 설명합니다. 나는 왜 그렇게 보이는 것처럼 작동해야하는지 설명 할 수 없습니다. 창조적 인 도약의 몰락.

주 : 무작위 샘플을 생성하는 많은 다른 절차는 명확하게 편향된 샘플 (즉, 상이한 모양 및 고도로 중첩되지 않는 커넬 밀도 곡선)을 산출한다.

Answer 1

예. Conjugation은 전체적인 연산이므로 각 파티션은 고유 한 공액 (conjugate)으로 매핑되고 다시 원래의 파티션으로 매핑됩니다. 그러므로 임의로 균등하게 선택된 파티션의 공역을 취함으로써 어떤 편향도 도입 될 수 없다.

이렇게하면 고정 길이 파티션을 무작위로 생성하는 데 도움이되지 않습니다. Nijenhuis & Wilf의 알고리즘을 올바르게 적용해야합니다. k 부분에 대한 n의 분할 수를 쉽게 계산할 수 있고 무작위 생성 알고리즘은 실제로 이것에만 의존하기 때문에 이렇게하기가 어렵지 않습니다.

크 누스는 TAOCP 볼륨 4A의 섹션 7.2.4.1에서 임의의 파티션을 생성하는 연습 (47)을 포함합니다. 이것은 무작위로 균일하게 고정 된 길이의 파티션을 생성하는 효율적인 알고리즘을위한 훌륭한 출발점이 될 것입니다.