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 を選択すれば、再帰的に木を構築することができる。

 

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

  

コード

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]