找到一組給定條件的最小數量的子集的算法

對於給定的一組數字{12,13,15,21,22,26,6,14,27,28,29,30,39,40,4,17,25}我想找到滿足這兩個條件的子集的最小數目。找到一組給定條件的最小數量的子集的算法

數在各組元件是一個常數即說上面例如它是5。
在子集中的任何一個滿足條件： (num1-num2)% d != 0。 num1>num2和其中d是兩個數之間的恆定差。

對於上面的例子：如果d=4和數量的子集的元素是5則子集的一個是：{12,13,15,22,17}

我在尋找一種算法來找到子集的最小數量滿足條件。

2016-04-17 Mrutyunjay

那麼，你可以蠻力吧:) – zegkljan

最有可能，你將別無選擇，只能蠻橫，因爲這比「揹包」式的問題稍微複雜一些。這些條件不一定只適用於一個元素，所以沒有辦法在不知道該特定子集的其他元素的情況下過濾出子集的潛在成員，因此在條件甚至可以被測試之前必須選擇子集（儘管％d！= 0與常數差異相矛盾）。由於找到最小數量的子集是需求，而不是找到任何匹配的子集，這將是一個非常計算密集的問題。 –

你說'd'是兩個數之間的常數差，那麼如何設置{12,13,15,22,17}'滿足這個？ –

好的，所以它不是100％的編程。這是一個標準的離散數學練習。

讓我們開始吧步驟：

金額所有可能的子集的組合：N！其中n是第一組元素的數量。我假設我們不允許在子集中重複選定的元素。和元素的子集的順序並不重要（否則我們就需要使用組合，而不是排列）
現在我們只選擇[R元素，並不是所有的ň他們，所以現在它的n！/（nr）！其中r是子集中元素的數量。
最難的部分完成。現在我們需要添加一個條件，爲此您只能使用先前的n！/（n-r）！和「壞」元素對的減量。基本上，排除任何從禁止值開始的排列。讓我們找到所有禁止的值：
兩個簡單的嵌套循環，檢查每個對的（num1-num2）％d！= 0，這將花費n *（n-1）/ 2次迭代。或者只需n^2次迭代就可以不用動態地改變嵌套循環中的迭代器。

來源

2016-04-17 06:13:33 Cthulchu

你可以解決這個貪婪。

將你的集合劃分爲S [i]，其中最初S [i] = {s in S使得s％d == i}。

然後，重複選擇k（在您的示例中爲5）最大的子集S [i]並從每個子集中移除一個元素。

下面是實現這一些略微低效但簡單的代碼：

def part(S, k, d): 
    "Split S into subsets of size<=d, each with elements unique mod k" 
    parts = [[] for _ in xrange(k)] 
    for s in S: 
     parts[s % k].append(s) 
    while sum(len(p) for p in parts): 
     parts.sort(key=len, reverse=True) 
     yield [x.pop() for x in parts[:d] if x] 

S = [12,13,15,21,22,26,6,14,27,28,29,30,39,40,4,17,25] 
for s in part(S, 6, 5): 
    print sorted(s)

輸出此代碼，其示出了至多5大小的子集，使得沒有子集包含兩個數等於模6：

[4, 14, 25, 30, 39] 
[6, 13, 17, 27, 40] 
[12, 21, 26, 28, 29] 
[15, 22]

parts這種排序條件可以通過優先級隊列和運行計數器進行優化，但會掩蓋正在發生的事情。優化後的表單將在O（n log n）時間運行;因爲它是O（n^2日誌n）

[我應該說，我非常肯定這個解決方案是正確的，但我不太明白如何證明它。我很希望看到證明（或反以顯示它是錯的）

來源

2016-04-17 06:13:41

我會做這樣的事情：

def run(self, n,m): 
     if len(n)<=1: 
     return [n]    
     x = n[0:1] //get 1st part 
     y = n[1:] //get remaining 
     t = self.run(y,m) 
     r=[] 
     if t: 
      r+=[x] //add current element 
      r+=[i for i in t if count(i)<=m] // add fixed combinations 
      r+=[ i+x for i in t if valid(i+x)] // all combined combinations 
     return r 
def valid(combination): 
    //code to check your condition 
    (num1-num2)% d != 0

來源

2016-04-17 08:14:41 thepiyush13

找到一組給定條件的最小數量的子集的算法

回答

相關問題