6

我一直在使用random_element()SAGE 提供的函数为给定整数 ( N) 生成特定长度 ( S) 的随机整数分区。我正在尝试从给定值的所有分区中生成无偏随机样本N和S。SAGE 的函数快速返回 N（即Partitions(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并且似乎产生了无偏样本（我已经针对 和 的各种值检查了整个分区集的结果N）S。

但是，我使用的 N (eg 10,000) 和 S (eg 300) 的值甚至使这种方法变得不切实际地缓慢。与 SAGErandom_element()功能相关的评论承认有很大的优化空间。那么，有没有办法通过不生成不匹配的分区来更快地生成匹配给定值的整数分区的无偏（即随机均匀）样本N和？此外，在许多情况下，使用共轭分区可以很好地生成无偏样本，但我不能说我完全理解为什么。 SS

4

3 回答 3

5

最后，我有一个绝对无偏的方法，拒绝率为零。当然，我已经对其进行了测试，以确保结果是整个可行集的代表性样本。它非常快而且完全没有偏见。享受。

from sage.all import *
import random

首先，一个函数用于找到 n 和 s 部分的分区的最小最大加数

def min_max(n,s):

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

    return _min

接下来，一个函数使用缓存和记忆来查找 n 的分区数，其中 s 部分以 x 为最大部分。这很快，但我认为有一个更优雅的解决方案。例如，经常： P(N,S,max=K) = P(NK,S-1) 感谢 ante ( https://stackoverflow.com/users/494076/ante ) 帮助我解决这个问题： Finding the number给定总数、部分数和最大和数的整数分区

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)]

最后，一个函数可以找到 n 和 s 部分的均匀随机分区，并且没有拒绝率！每个随机选择的数字编码用于具有 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

当我试图计算强生日问题的概率时，我遇到了类似的问题。

首先，仅给定少量数字时，分区函数就会爆炸。你会返回很多信息。无论您使用哪种方法，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 回答
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 回答