具有給定約束條件的分區數量

請考慮一組13個丹麥語，11個日語和8個波蘭人。衆所周知，將這組人分爲不同的方式的數量是13 + 11 + 8 = 32：Bell個數（設置分區的數量）。然而，我們被要求在給定的約束條件下找到可能的分區數量。現在的問題是：具有給定約束條件的分區數量

一組分區據說是好，如果它沒有組由至少兩個人的那只有包括單一國籍。這個集合有多少個好的分區？（一個小組可能只包括一個人。）

蠻力方法需要通過大約10^26個分區並檢查哪些是好的。這似乎是不可行的，特別是如果這些團體更大或者介紹其他國籍的話。有沒有一種聰明的方式呢？

編輯：作爲一個附註。可能沒有希望有一個非常好的解決方案。一位備受尊敬的combinatorics專家answered的一個相關問題，我認爲這個問題基本上說相關問題，因此這個問題也很難準確解決。

來源

2015-11-30 Azizi

以及你在那裏也問過它並得到了你的答案國際海事組織你可以在這裏關閉 – Carsten

由於表達式中的一些非線性因素，生成函數非常難以應用。獲得它的洞察力非常好，它告訴我們關於這個問題的一些事情。然而，不是，我正在尋找的確切數字。 – Azizi

[This]（http://math.stackexchange.com/a/25516/66856）討論了生成函數的好處。實際上獲得數字需要一個聰明的算法（或可笑的計算能力）。 – Azizi

這是一個使用動態編程的解決方案。

它從一個空集開始，然後每次添加一個元素並計算所有有效的分區。

狀態空間是巨大，但是請注意，要能計算出下一步，我們只需要知道一個分區以下的事情：

對於每一個民族，有多少套包含只由該國籍的一名成員組成。（例如：{a}）
它包含多少個具有混合元素的集合。（例如：{a，b，c}）

對於這些配置中的每一種，我只存儲總數。例如：

[0, 1, 2, 2] -> 3 
{a}{b}{c}{mixed} 
    e.g.: 3 partitions that look like: {b}, {c}, {c}, {a,c}, {b,c}

這裏是在Python代碼：

import collections 
from operator import mul 
from fractions import Fraction 

def nCk(n,k): 
    return int(reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1)) 

def good_partitions(l): 
    n = len(l) 
    i = 0 
    prev = collections.defaultdict(int) 
    while l: 
     #any more from this kind? 
     if l[0] == 0: 
      l.pop(0) 
      i += 1 
      continue 
     l[0] -= 1 
     curr = collections.defaultdict(int) 

     for solution,total in prev.iteritems(): 
      for idx,item in enumerate(solution): 
       my_solution = list(solution) 
       if idx == i: 
        # add element as a new set 
        my_solution[i] += 1 
        curr[tuple(my_solution)] += total 
       elif my_solution[idx]: 
        if idx != n: 
         # add to a set consisting of one element 
         # or merge into multiple sets that consist of one element 
         cnt = my_solution[idx] 
         c = cnt 
         while c > 0: 
          my_solution = list(solution) 
          my_solution[n] += 1 
          my_solution[idx] -= c 
          curr[tuple(my_solution)] += total * nCk(cnt, c) 
          c -= 1 
        else: 
         # add to a mixed set 
         cnt = my_solution[idx] 
         curr[tuple(my_solution)] += total * cnt 

     if not prev: 
      # one set with one element 
      lone = [0] * (n+1) 
      lone[i] = 1 
      curr[tuple(lone)] = 1 

     prev = curr 
    return sum(prev.values()) 

print good_partitions([1, 1, 1, 1])  # 15 
print good_partitions([1, 1, 1, 1, 1]) # 52 
print good_partitions([2, 1])   # 4 
print good_partitions([13, 11, 8])  # 29811734589499214658370837

它的測試案例產生正確的價值觀。我還用一個蠻力解決方案（對於小數值）測試了它，並且它產生了相同的結果。

來源

2015-11-30 23:53:22

此解決方案適用！謝謝，幹得好！ – Azizi

精確的分析解決方案很難，但多項式時間+空間動態規劃解決方案非常簡單。

首先，我們需要一個關於組的大小的絕對順序。我們通過比較我們有多少丹麥人，日本人和波蘭人來做到這一點。

接下來，寫入的函數就是這一個。

m is the maximum group size we can emit 

p is the number of people of each nationality that we have left to split 

max_good_partitions_of_maximum_size(m, p) is the number of "good partitions" 
we can form from p people, with no group being larger than m

顯然，你可以這樣寫的有點複雜的遞歸函數總是選擇下一個分區使用，然後調用本身與作爲新的最大尺寸，並從對減去分區。如果你有這個功能，那麼你的答案就是max_good_partitions_of_maximum_size(p, p)和p = [13, 11, 8]。但是這將是一場不可能在合理時間內運行的強力搜索。

最後應用https://en.wikipedia.org/wiki/Memoization緩存對此函數的每次調用，並且它將以多項式時間運行。但是，您還必須緩存一個多項式的呼叫號碼。

來源

2015-11-30 18:51:16 btilly

具有給定約束條件的分區數量

回答

相關問題