如何找到一組所有可能的n元素子集？

-1

對於一組k -elements，我需要找到所有可能的n -element子集(n < k)。如何找到一組所有可能的n元素子集？

我該如何解決這個問題？

只是一個建議將有幫助謝謝！

來源

2013-07-02 user1315305

'我應該如何處理這個problem.'筆和紙在思考算法時效果最佳。 –

@nickecarlo這真的很有幫助，謝謝... – user1315305

@ user1315305問題標記爲-ve，因爲錯誤標籤，問題對我來說也很典型 –

我在topcoder的算法教程中看到了這一點。花了一些時間並瞭解它是如何工作的。

迭代通過所有的k元素子集{0,1，... N-1}

int s = (1 << k) - 1; 
    while (!(s & 1 << N)) 
    { 
    // do stuff with s 
    int lo = s & ~(s - 1);  // lowest one bit 
    int lz = (s + lo) & ~s;  // lowest zero bit above lo 
    s |= lz;      // add lz to the set 
    s &= ~(lz - 1);    // reset bits below lz 
    s |= (lz/lo/2) - 1;  // put back right number of bits at end 
    }

來源

2013-07-02 21:11:04 Aravind

雖然它通常是非常高效的，但是位魔法是溝通算法思想的一種不好的方式。 –

@ G.Bach：可能比緩慢解決問題的算法更好地傳達快速解決問題的算法。特別是當你評論它，以便它是可理解的。沒有？ – tmyklebu

@tmyklebu當然，更好的複雜算法是可取的，評論確實有幫助。但是當我知道這段代碼應該達到什麼時，我不明白它是如何工作的。 –

當我需要獲取Java中的字符串ArrayList的所有組合（或子集）時，我使用了這種方法。

public static List<List<String>> powerset(ArrayList<String> list) { 
     List<List<String>> ps = new ArrayList<List<String>>(); 
     ps.add(new ArrayList<String>()); 

     // for every item in the original list 
     for (String item : list) { 
      List<List<String>> newPs = new ArrayList<List<String>>(); 

      for (List<String> subset : ps) { 
       // copy all of the current powerset's subsets 
       newPs.add(subset); 

       // plus the subsets appended with the current item 
       List<String> newSubset = new ArrayList<String>(subset); 
       newSubset.add(item); 
       newPs.add(newSubset); 
      } 

      // powerset is now powerset of list.subList(0, list.indexOf(item)+1) 
      ps = newPs; 
     } 
     return ps; 
}

這是一個昂貴的操作，可能不是您的情況的完美解決方案。但是，如果我想盡快提出解決方案，我會按照這些方法做一些事情。您可以檢查newSubset是否小於n，即所需子集的大小，如果它小於n，則只能將item添加到該子集。這會阻止你生成大於n的子集。最後，您可以遍歷ps並刪除任何小於n的數組列表。再次，這個解決方案絕不是完美的......但它應該訣竅

來源

2013-07-02 20:21:02 sunrize920

我喜歡這種組合方法，並且考慮到它是你正在構建的一個權力集合，它對我來說並不壞。但是，如果工作僅僅是獲得具有固定數量元素的子集，構建功率集合的成本就會成倍地增加。 –

@ sunrize920謝謝！ – user1315305

不幸的是，我用盡了子集大小= 21的內存，並設置大小= 60，所以我必須找到一些更好的解決方案。 – user1315305

句子：集A被設定整數的小於10

寫爲：

A={0,1,2,3,4,5,6,7,8,9}

它被稱爲上市或名冊方法

來源

2014-06-04 12:34:35 Chloe

如何找到一組所有可能的n元素子集？

回答

相關問題