枚舉集合的分區爲相同大小的子集

我有一個集合，我想將它分成包含相等數量的元素的子集。枚舉集合的分區爲相同大小的子集

我正在尋找一種快速算法，最好不要啓發式算法。

提示：

if n= number of elements in the main set 
    l= number of elements in each subset

蠻力算法是：

1-x < - 所有的在一個時間而不重複採取L N的東西的組合。 | x | = nCl = n！/（l！*（n-1）！）
2-y < - 全部 x個事物的組合，一次不重複。 | y | = xCn

3-在y中選擇子集，例如它們的元素中沒有任何重疊。

答案的數目是：

n!/(l!^(n/l)*(n/l)!)

例如，如果S={a,b,c,d}並且如果與2個元素的子集來分區集S被期望：

集合X是：

(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)

集y（潛在答案）是：

{(a,b),(a,c)} 
{(a,b),(a,d)} 
{(a,b),(b,c)} 
{(a,b),(b,d)} 
{(a,b),(c,d)}  
{(a,c),(a,d)} 
{(a,c),(b,c)} 
{(a,c),(b,d)} 
{(a,c),(c,d)} 
{(a,d),(b,c)} 
{(a,d),(b,d)} 
{(a,d),(c,d)} 
{(b,c),(d,d)} 
{(b,c),(c,d)} 
{(b,d),(c,d)}

和正確的答案是：只有當n爲小

S1={(a,b),(c,d)} 
S2={(a,c),(b,d)} 
S3={(a,d),(b,c)}

所提到的算法是非常有用的。例如，當：

n=90, l=3 => 
|x|=117480 
|y|=1.28827732e+318 
and the number of correct answers is `2.533601e+82`.

因此算法不是最實用的情況下，由於時間的性能和內存的問題。

即使擁有並運行高效的算法，結果的數量也會很大，因此會很耗時。例如在上面的問題中，答案的數量= 2.533601e+82

我不是集合論的專業知識，所以也許這是一個衆所周知的問題。

感謝您的幫助。

來源

2014-02-28 user3362866

你能告訴我們你在解決自己問題的嘗試？ – Dukeling

你會有更好的運氣，包括你的嘗試和詢問代碼本身，而不是要求抽象的解決方案。 – leigero

我在問題 – user3362866

我認爲這可能是關閉...希望你使用的是Java

public static void main(String[] args) { 
    ArrayList<String> tokens = new ArrayList(new TreeSet<>(Arrays.asList(new String[]{"a","b","c","d"}))); 

    for (int i = 0; i < tokens.size(); i++) { 
     String tokenA = tokens.get(i); 
     for (int x = (i + 1); x < tokens.size(); x++) { 
     String tokenB = tokens.get(x); 
     //String tokenC = tokens.get(x + 1); 

     System.out.println(tokenA + "-" + tokenB); 
     } 
    } 
    }

我的輸出是

run: 
a-b 
a-c 
a-d 
b-c 
b-d 
c-d 
BUILD SUCCESSFUL (total time: 0 seconds)

來源

2014-02-28 02:39:34 markg

感謝您的回答，但它只是提供了所有與2個元素的組合 – user3362866

，認爲它可能使一個體面的起點 – markg

在R中，上述程序可能寫成combn（字母[1：4]，2）''。儘管如此，仍然沒有回答這個問題。 –

枚舉集合的分區爲相同大小的子集

回答

相關問題