以下は、K 部分で N の整数パーティションを表す整数を再コーディングする限り、私が求めたことを達成するスクリプトです。このアプローチが K > 4 の場合に実用的であるためには、より優れた再コーディング方法が必要です。しかし、それは概念的に単純であり、根本的に公平であると簡単に主張できます。小さな K に対しても非常に高速です。スクリプトは Sage ノートブックで問題なく実行され、Sage 関数は呼び出されません。これはランダム サンプリング用のスクリプトではありません。ランダム サンプリング自体は問題ではありません。
メソッド:
1.) 整数パーティションを、それらの被加数が連結され、最初のレキシカル パーティション内の最大の被加数のサイズに応じてゼロが埋め込まれているかのように扱います。たとえば、[17,1,1,1] -> 17010101 & [5,5,5,5 ] -> 05050505
2.) 結果の整数を、最大の整数 (つまり、最初の字句区分を表す int) から減算したかのように扱います。例: 17010101 - 5050505 = 11959596
3.) 減少した整数を共通の分母で割ったものとして扱います。たとえば、11959596/99 = 120804 です。
したがって、ランダムなパーティションを選択したい場合は、次のようにします。
1.) 0 から 120,804 の間の数値を選択します (5,050,505 から 17,010,101 の間の数値ではなく)
2.) 数値に 99 を掛けて、17010101 から引きます。
3.) 各整数を 0 で埋めたものとして処理した方法に従って、結果の整数を分割します。
長所と短所:質問の本文で述べたように、この特定の再コーディング方法では、P のメンバーを表す整数をランダムに選択する可能性を大幅に改善するのに十分ではありません。より大きな合計、たとえば N > 100 の場合、この概念を実装する関数は非常に高速になる可能性があります。これは、他のランダム分割関数を遅くしたり、大きな N を処理するために他の関数を非実用的にしたりするタイムリーな再帰 (ヘビが尻尾を食べる) を回避するためです。
K が小さい場合、P のメンバーを描画する確率は、残りのプロセスの速度を考慮すると妥当です。迅速なランダム描画、デコード、および評価と組み合わせることで、この関数は、他のアルゴリズムでは不可能な N&K (たとえば、N = 20000、K = 4) の組み合わせに対して均一なランダム パーティションを見つけることができます。これを一般的に強力なアプローチにするためには、整数を再コード化するためのより良い方法が大いに必要です。
import random
import sys
まず、いくつかの一般的に便利で簡単な関数
def first_partition(N,K):
part = [N-K+1]
ones = [1]*(K-1)
part.extend(ones)
return part
def last_partition(N,K):
most_even = [int(floor(float(N)/float(K)))]*K
_remainder = int(N%K)
j = 0
while _remainder > 0:
most_even[j] += 1
_remainder -= 1
j += 1
return most_even
def first_part_nmax(N,K,Nmax):
part = [Nmax]
N -= Nmax
K -= 1
while N > 0:
Nmax = min(Nmax,N-K+1)
part.append(Nmax)
N -= Nmax
K -= 1
return part
#print first_partition(20,4)
#print last_partition(20,4)
#print first_part_nmax(20,4,12)
#sys.exit()
def portion(alist, indices):
return [alist[i:j] for i, j in zip([0]+indices, indices+[None])]
def next_restricted_part(part,N,K): # *find next partition matching N&K w/out recursion
if part == last_partition(N,K):return first_partition(N,K)
for i in enumerate(reversed(part)):
if i[1] - part[-1] > 1:
if i[0] == (K-1):
return first_part_nmax(N,K,(i[1]-1))
else:
parts = portion(part,[K-i[0]-1]) # split p
h1 = parts[0]
h2 = parts[1]
next = first_part_nmax(sum(h2),len(h2),(h2[0]-1))
return h1+next
""" *I don't know a math software that has this function and Nijenhuis and Wilf (1978)
don't give it (i.e. NEXPAR is not restricted by K). Apparently, folks often get the
next restricted part using recursion, which is unnecessary """
def int_to_list(i): # convert an int to a list w/out padding with 0'
return [int(x) for x in str(i)]
def int_to_list_fill(i,fill):# convert an int to a list and pad with 0's
return [x for x in str(i).zfill(fill)]
def list_to_int(l):# convert a list to an integer
return "".join(str(x) for x in l)
def part_to_int(part,fill):# convert an int to a partition of K parts
# and pad with the respective number of 0's
p_list = []
for p in part:
if len(int_to_list(p)) != fill:
l = int_to_list_fill(p,fill)
p = list_to_int(l)
p_list.append(p)
_int = list_to_int(p_list)
return _int
def int_to_part(num,fill,K): # convert an int to a partition of K parts
# and pad with the respective number of 0's
# This function isn't called by the script, but I thought I'd include
# it anyway because it would be used to recover the respective partition
_list = int_to_list(num)
if len(_list) != fill*K:
ct = fill*K - len(_list)
while ct > 0:
_list.insert(0,0)
ct -= 1
new_list1 = []
new_list2 = []
for i in _list:
new_list1.append(i)
if len(new_list1) == fill:
new_list2.append(new_list1)
new_list1 = []
part = []
for i in new_list2:
j = int(list_to_int(i))
part.append(j)
return part
最後に、合計 N とパーツ数 K を取得します。以下は、関連する再コード化された整数とともに、N&K を満たすパーティションを字句順に出力します。
N = 20
K = 4
print '#, partition, coded, _diff, smaller_diff'
first_part = first_partition(N,K) # first lexical partition for N&K
fill = len(int_to_list(max(first_part)))
# pad with zeros to 1.) ensure a strictly decreasing relationship w/in P,
# 2.) keep track of (encode/decode) partition summand values
first_num = part_to_int(first_part,fill)
last_part = last_partition(N,K)
last_num = part_to_int(last_part,fill)
print '1',first_part,first_num,'',0,' ',0
part = list(first_part)
ct = 1
while ct < 10:
part = next_restricted_part(part,N,K)
_num = part_to_int(part,fill)
_diff = int(first_num) - int(_num)
smaller_diff = (_diff/99)
ct+=1
print ct, part, _num,'',_diff,' ',smaller_diff
出力：
ct、パーティション、コード化、_diff、smaller_diff
1 [17, 1, 1, 1] 17010101 0 0
2 [16, 2, 1, 1] 16020101 990000 10000
3 [15、3、1、1] 15030101 1980000 20000
4 [15, 2, 2, 1] 15020201 1989900 20100
5 [14、4、1、1] 14040101 2970000 30000
6 [14、3、2、1] 14030201 2979900 30100
7 [14、2、2、2] 14020202 2989899 30201
8 [13、5、1、1] 13050101 3960000 40000
9 [13、4、2、1] 13040201 3969900 40100
10 [13、3、3、1] 13030301 3979800 40200
つまり、最後の列の整数は、はるかに小さい可能性があります。
この考えに基づくランダム サンプリング戦略が基本的に公平である理由:
K 個の部分を持つ N の各整数パーティションは、1 つの再コード化された整数にのみ対応します。つまり、数字を無作為に選んでデコードし、要素を再配置して N&K の適切な分割を形成しようとすることはありません。したがって、各整数 (N&K のパーティションに対応するかどうかに関係なく) が描画される可能性は同じです。目標は、N と K の部分に対応しない整数の数を本質的に減らすことであり、ランダム サンプリングのプロセスを高速化することです。