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 を選択すれば、再帰的に木を構築することができる。
なお、木構造ではなく線形に順次リストを作っていく方法も可能だが
再帰にした場合にスタック溢れが起きてしまうこと、また大きな値が前方に偏ってしまうことから採用を見送った。
コード
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)
- 実行例
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])
- 出力例
[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]
