將n分爲有限制的k部分

我需要一種算法，將n數字分區生成k部分，並附加限制條件，即分區的每個元素必須介於a和b之間。理想情況下，滿足限制條件的所有可能的分區應該是同等可能的如果分區按照不同的順序具有相同的元素，則認爲它們是相同的。將n分爲有限制的k部分

例如，對於n=10，k=3，a=2，b=4一個僅具有{4,4,2}和{4,3,3}作爲可能的結果。

是否有這樣一個問題的標準算法？可以假定至少有一個滿足限制條件的分區總是存在。

來源

2017-02-01 gunbl4d3

我最近回答了一個非常類似的問題，與相應的計算條件概率和樣品的算法：http://stackoverflow.com/q/41871179/2144669 –

您可以將其實現爲遞歸算法。基本上，復發是這樣的：

如果k == 1和a <= n <= b，那麼唯一的分區是[n]，否則無
否則，從a與所有的分區合併所有元素x到b爲n-x，k-1
以防止重複，也替換下界a與x

下面是一些Python（又名可執行僞代碼）：

def partitions(n, k, a, b): 
    if k == 1 and a <= n <= b: 
     yield [n] 
    elif n > 0 and k > 0: 
     for x in range(a, b+1): 
      for p in partitions(n-x, k-1, x, b): 
       yield [x] + p 

print(list(partitions(10, 3, 2, 4))) 
# [[2, 4, 4], [3, 3, 4]]

這可以通過檢測用於所述剩餘元件，分別在下限和上限(k-1)*a和(k-1)*b，並限制範圍x因此可以進一步提高：

 min_x = max(a, n - (k-1) * b) 
     max_x = min(b, n - (k-1) * a) 
     for x in range(min_x, max_x+1):

對於partitions(110, 12, 3, 12)有3,157的解決方案，這將減小從638679遞歸調用到24135的號碼。

來源

2017-02-01 15:07:01

嗯，我錯過了你想要一個單一的隨機分區，而不是整個列表的部分......好吧，你仍然可以生成它們，然後隨機挑一個。這也可以保證每個法定排列的可能性相同。 –

如果k和b - a不是太大，你可以嘗試隨機深度優先搜索：

import random 

def restricted_partition_rec(n, k, min, max): 
    if k <= 0 or n < min: 
     return [] 
    ps = list(range(min, max + 1)) 
    random.shuffle(ps) 
    for p in ps: 
     if p > n: 
      continue 
     elif p < n: 
      subp = restricted_partition(n - p, k - 1, min, max) 
      if subp: 
       return [p] + subp 
     elif k == 1: 
      return [p] 
    return [] 

def restricted_partition(n, k, min, max): 
    return sorted(restricted_partition_rec(n, k, min, max), reverse=True) 

print(restricted_partition(10, 3, 2, 4)) 
>>> 
[4, 4, 2]

雖然我不知道如果所有分區都恰好在這種情況下，相同的概率。

來源

2017-02-01 15:04:37 jdehesa

我的興趣從38 N到的值110，k從6到12，a = 3，b = 12 – gunbl4d3

這是一個使用條件概率的抽樣算法。

import collections 
import random 

countmemo = {} 


def count(n, k, a, b): 
    assert n >= 0 
    assert k >= 0 
    assert a >= 0 
    assert b >= 0 
    if k == 0: 
     return 1 if n == 0 else 0 
    key = (n, k, a, b) 
    if key not in countmemo: 
     countmemo[key] = sum(
      count(n - c, k - 1, a, c) for c in range(a, min(n, b) + 1)) 
    return countmemo[key] 


def sample(n, k, a, b): 
    partition = [] 
    x = random.randrange(count(n, k, a, b)) 
    while k > 0: 
     for c in range(a, min(n, b) + 1): 
      y = count(n - c, k - 1, a, c) 
      if x < y: 
       partition.append(c) 
       n -= c 
       k -= 1 
       b = c 
       break 
      x -= y 
     else: 
      assert False 
    return partition 


def test(): 
    print(collections.Counter(
     tuple(sample(20, 6, 2, 5)) for i in range(10000))) 


if __name__ == '__main__': 
    test()

來源

2017-02-01 23:16:32

將n分爲有限制的k部分

回答

相關問題