6

私はSAGEが提供する関数を使用して、特定の長さ（）である特定のrandom_element()整数（）のランダムな整数パーティションを生成してきました。との特定の値に対して、すべてのパーティションのセットからバイアスのないランダムサンプルを生成しようとしています。SAGEの関数は、N（つまり）のランダムパーティションをすばやく返します。NSNSPartitions(N).random_element()

ただし、追加するとS（つまりPartitions(N,length=S).random_element()）、非常に遅くなります。N同様に、長さが長いランダムなパーティションを除外するのSは非常に時間がかかります。

ただし、これが誰かに役立つことを願っています。関数が長さにN一致しないパーティションを返す場合S、共役パーティションの長さはSであることがよくあります。つまり、次のようになります。

S = 10
N = 100
part = list(Partitions(N).random_element())
    if len(part) != S:
        SAD = list(Partition(part).conjugate())
        if len(SAD) != S:
            continue

これにより、長さのパーティションが検出される速度が上がり、偏りのないサンプルが生成されるように見えます（とのさまざまな値について、Sパーティションのセット全体に対して結果を調べました）。NS

ただし、私はN（eg 10,000）とS（eg）の値を使用し300ているため、このアプローチでさえも実用的ではありません。SAGEのrandom_element()機能に関連するコメントは、最適化の余地が十分にあることを認めています。それで、おそらく、一致しないパーティションを生成しないことによって、Nとの特定の値に一致する整数パーティションのバイアスのない（つまりランダムに均一な）サンプルをより迅速に生成する方法はありますか？さらに、共役パーティションを使用すると、多くの場合、偏りのないサンプルを生成できますが、その理由を正確に理解しているとは言えません。 SS

4

3 に答える 3

5

最後に、拒否率がゼロの、明確に偏りのない方法があります。もちろん、結果が実行可能セット全体の代表的なサンプルであることを確認するためにテストしました。それは非常に高速で完全に偏りがありません。楽しみ。

from sage.all import *
import random

まず、s個の部分を持つn個のパーティションの最小の最大加数を見つける関数

def min_max(n,s):

    _min = int(floor(float(n)/float(s)))
    if int(n%s) > 0:
        _min +=1

    return _min

次に、キャッシュとメモ化を使用して、xを最大部分とするs個の部分を持つn個のパーティションの数を見つける関数。これは高速ですが、もっとエレガントな解決策があると思います。例：多くの場合：P（N、S、max = K）= P（NK、S-1）これを手伝ってくれ たante（ https://stackoverflow.com/users/494076/ante ）に感謝します：番号を見つける合計、部分の数、および最大被加数が与えられた整数パーティションの数

D = {}
def P(n,s,x):
    if n > s*x or x <= 0: return 0
    if n == s*x: return 1
    if (n,s,x) not in D:
        D[(n,s,x)] = sum(P(n-i*x, s-i, x-1) for i in xrange(s))
    return D[(n,s,x)]

最後に、棄却率なしで、s個の部分を持つnの均一なランダム分割を見つける関数！ランダムに選択された各番号は、s個の部分を持つnの特定のパーティションに対してコード化されます。

def random_partition(n,s):
    S = s
    partition = []
    _min = min_max(n,S)
    _max = n-S+1

    total = number_of_partitions(n,S)
    which = random.randrange(1,total+1) # random number

    while n:
        for k in range(_min,_max+1):
            count = P(n,S,k)
            if count >= which:
                count = P(n,S,k-1)
                break

        partition.append(k)
        n -= k
        if n == 0: break
        S -= 1
        which -= count
        _min = min_max(n,S)
        _max = k

    return partition
于 2012-10-05T08:35:42.757 に答える
0

簡単なアプローチ：整数をランダムに割り当てます。

def random_partition(n, s):
    partition = [0] * s
    for x in range(n):
        partition[random.randrange(s)] += 1
    return partition
于 2012-04-23T19:46:16.343 に答える
0

強い誕生日の問題の確率を計算しようとしたときに、同様の問題が発生しました。

まず、適度な数だけが与えられると、分配関数が爆発します。あなたはたくさんの情報を返すでしょう。N=10000およびS=300を使用している方法に関係なく、途方もない量のデータが生成されます。遅くなります。使用する純粋なPython実装は、同じように遅くなるか遅くなる可能性があります。CModuleの作成を検討してください。

Pythonを試してみたい場合は、メモリ使用量を抑えるためにitertoolsとジェネレーターの組み合わせとして採用したアプローチを使用してください。私のコードはもう手元にないようですが、ここに良い実装があります：

http://wordaligned.org/articles/partitioning-with-python

編集：

私のコードが見つかりました：

def partition(a, b=-1, limit=365):
  if (b == -1):
    b = a
  if (a == 2 or a == 3):
    if (b >= a and limit):
      yield [a]
    else:
      return
  elif (a > 3):
    if (a <= b):
      yield [a]
    c = 0
    if b > a-2:
      c = a-2
    else:
      c = b
    for i in xrange(c, 1, -1):
      if (limit):
        for j in partition(a-i, i, limit-1):
          yield [i] + j
于 2012-04-23T19:47:44.683 に答える