將組劃分爲大小爲k的子羣

Question

我陷入了一個問題： 找到將大小爲'n'的組劃分爲大小爲'k'的子羣的所有可能方法。 （這裏n％k = 0）

例如，令集{1,2,3,4,5,6}劃分成3個子集（k = 3，n = 6），可能集是

一個）{1,2,3}，{4,5,6}

b）{1,3,5}，{2,4,6}

C）{ 1,3,6}，{2,4,5}

d）{1,3,4}，{2,5,6}等....

什麼，我試圖做首先是找到所有大小爲k的組合。 然後通過這些組合循環查找哪些所有組合可以組合在一起以查找子組列表。

但我相信這種方法的時間複雜性非常糟糕。這個問題有沒有更好的方法？

Answer 1

我會使用遞歸方法。我認爲這個有最佳的運行時間，因爲它確實產生了所有需要的子集。

public static void solve(int[] a, int k, int i, List<List<Integer>> subsets) { 
    if (i == a.length) { 
     for (List<Integer> subset : subsets) { 
      System.out.print(subset);    
     } 
     System.out.println(); 
    } else { 
     // loop over all subsets and try to put a[i] in 
     for (int j = 0; j < subsets.size(); j++) {     
      if (subsets.get(j).size() < k) { 
       // subset j not full 
       subsets.get(j).add(a[i]); 
       solve(a, k, i+1, subsets); // do recursion 
       subsets.get(j).remove((Integer)a[i]); 

       if (subsets.get(j).size() == 0) { 
        // don't skip empty subsets, so you won't get duplicates 
        break; 
       }      
      } 
     } 
    } 
} 

用法：

public static void main(String[] args) { 
    int[] a = {1, 2, 3, 4, 5, 6}; 
    int k = 3; 

    List<List<Integer>> subsets = new ArrayList<List<Integer>>(a.length/k); 
    for (int i = 0; i < a.length/k; i++) 
     subsets.add(new ArrayList<Integer>(k)); 
    solve(a, k, 0, subsets); 
} 

打印：

[1, 2, 3][4, 5, 6] 
[1, 2, 4][3, 5, 6] 
[1, 2, 5][3, 4, 6] 
[1, 2, 6][3, 4, 5] 
[1, 3, 4][2, 5, 6] 
[1, 3, 5][2, 4, 6] 
[1, 3, 6][2, 4, 5] 
[1, 4, 5][2, 3, 6] 
[1, 4, 6][2, 3, 5] 
[1, 5, 6][2, 3, 4] 

Answer 2

想想組合方法。如果n % k != 0，你不能這樣做，因爲你最終會得到一個小於k元素的集合，所以首先檢查是否是這種情況。

之後，您需要做的就是從n-i*k中爲所有i in [0; n/k]遞歸生成k組合。用於產生給定集合的所有k-組合的算法可以在SO上容易地找到。這個想法是：有（可選擇k個）可能的這樣的組合，你可以爲你的第一組選擇;從剩下的n-k元素中，可以選擇（（n-k）選擇k）集合）;從剩下的n-2k元素中，可以選擇（（n-2k）選擇k）集合等等。假設你的集合的順序無關緊要，你有(n choose k) * ((n-k) choose k) * ... * ((n-(n-1)k) choose k)/((n/k)!)選擇你的集合的可能性，這取決於k可以是原始集合中元素的數量的指數，所以如果你真的想要生成它們中的每一個，你不會低於指數複雜度。

Answer 3

我找到了可能的子分組＃的公式，以防萬一有人發現它有趣。 （這是否被認爲太離題了？我是否正確發佈了這個？）
首先讓m = n/k成爲子組的編號。現在讓第一個子組固定爲組的前k個元素，第二個子組爲下一個k，依此類推。如果我們考慮組的所有可能的排列組合，這將給我們所有不同的子組。有n個元素的排列有n!，但我們不關心排序，所以我們排除了每個子組的k!排列和子組本身的m!排列。這給了我們： n!/(m!*(k!)^m)。
作爲一個檢查，如果k = 1或k = n，這給了我們1個分組。在最初的例子中，n = 6，k = 3，m = 2，我們得到10個可能的子組（赫斯特的代碼找到）。
現在，如果您將此表達式與G.Bach給出並使用(n choose k) = n!/(k!*(n-k)!)的表達式進行比較，您將看到所有的(n-k)!項都被取消，並且它減少到上述表達式。
獎勵：如果您使用斯特林的n!近似值，則表達式可以很好地簡化，並且您將得到的子分組數量標度爲(m^n)/m!。