Python: Random Partition of Integer

Python: ランダムな整数分割の実装

目的

• 非負整数 n を 和を保ったまま m 個のバケットにランダムに分割したい
• そのとき、各バケットの内容が上限 k を超えないようにする。
• 制約
• 0 <= n < 2^31
• 1 <= m < 2^19
• 0 <= k < 2^31
• n <= m * k
• 言い換えれば、n, m, k が与えられた時に、以下を満たす数値のリスト x[i] (0 <= i < m) を
  ランダムに求めたい。
• ∀i (0 <= x[i] <= k)
• Σ x[i] = n

 

アイデア

二分木と再帰を使ってリストを作る。

動作イメージは以下のとおり。

 

m = 1 ならばそれは葉なので計算終了。(値は n)
それ以外は、ほぼ半数になるように m を左右に振り分ける。

振り分ける個数を左から順に m1, m2、振り分ける数値を n1, n2 とした場合、制約から

• a) n1 + n2 = n
• b) 0 <= n1
• c) 0 <= n2
• d) n1 <= m1 * k
• e) n2 <= m2 * k

を満たす必要がある。

 

e) に a) の n2 = n - n1 を代入すれば、n1 >= n - m2 * k という不等式が導けるので

n1 は以下の制約を持つことになる。 

• 0 <= n1 <= n    a), b), c) から
• n - m2 * k <= n1 <= m1 * k    a), d), e) から

この範囲内でランダムに n1 を選択すれば、再帰的に木を構築することができる。

 

なお、木構造ではなく線形に順次リストを作っていく方法も可能だが
再帰にした場合にスタック溢れが起きてしまうこと、また大きな値が前方に偏ってしまうことから採用を見送った。

  

コード

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

import random     def random_partition(size, total, upper):     assert(1 <= size <= 0x0007ffff)     assert(0 <= total <= 0x7fffffff)     assert(0 <= upper <= 0x7fffffff)     assert(total <= size * upper)       if size == 1:         return [total]       s1 = size / 2     s2 = size - s1     t1 = random.randint(max(0, total - s2 * upper), min(total, s1 * upper))     t2 = total - t1       return random_partition(s1, t1, upper) + random_partition(s2, t2, upper)

• 実行例

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

print(random_partition(1, 0, 0)) print(random_partition(1, 1, 1)) print(random_partition(10, 1000, 100)) print(random_partition(10, 1, 1)) print(random_partition(7, 10, 10000)) print(random_partition(0x0007ffff, 0x7fffffff, 0x7fffffff)[:10]) print(random_partition(0x0007ffff, 0x7fffffff, 0x7fffffff)[-10:]) print(random_partition(0x0007ffff, 0, 0)[:10]) print(random_partition(10000, 1000000000, 100000)[:10]) print(random_partition(1 << 18, 0, 1 << 12)[:10]) print(random_partition(1 << 18, 1, 1 << 12)[:10]) print(random_partition(1 << 18, 100000000, 1 << 12)[:10]) print(random_partition(1 << 18, 1000000000, 1 << 12)[:10]) print(random_partition(1 << 18, 1 << 18, 1)[:10]) print(random_partition(1 << 18, 1 << 30, 1 << 12)[:10])

• 出力例

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

[0] [1] [100, 100, 100, 100, 100, 100, 100, 100, 100, 100] [0, 0, 0, 0, 0, 0, 0, 1, 0, 0] [1, 3, 3, 0, 0, 0, 3] [16, 14, 5, 2, 5, 3, 4, 0, 1, 0] [1, 0, 0, 1, 0, 1, 0, 1, 0, 1] [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000] [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [176, 546, 366, 86, 1032, 169, 28, 155, 518, 188] [3934, 3915, 4078, 4082, 4095, 4095, 4094, 4095, 4038, 4015] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [4096, 4096, 4096, 4096, 4096, 4096, 4096, 4096, 4096, 4096]