将集合的分区枚举为大小相等的子集 [英] Enumerate partitions of a set into subsets of equal size
问题描述
我有一个集合,我想将其划分为包含相等数量元素的子集合。
I have a set and I want to partition it into sub-set containing equal number of element.
我正在寻找一种快速算法,最好不要使用启发式算法。
I am looking for a fast algorithm and preferably not heuristic one.
提示:
if n= number of elements in the main set
l= number of elements in each subset
蛮力算法是:
1-x<-一次取n物的所有组合没有
重复。 | x | = nCl = n!/(l!*(n-l)!)
2-y< -x的所有
组合,一次取n次,没有重复。 | y | = xCn
1-x <-All combinations of n things taken l at a time without repetition. |x|=nCl=n!/(l!*(n-l)!)
2-y <-All combinations of x things taken n at a time without repetition. |y|=xCn
3-选择y中的子集,例如在其
元素内没有任何重叠。
3-Select subsets in y such as there is no any overlap within their elements.
答案的数量为:
n!/(l!^(n/l)*(n/l)!)
例如,如果 S = {a,b,c,d}
,如果需要具有2个元素的子集来划分集合S:
For instance if S={a,b,c,d}
and if subsets with 2 elements to partition set S is desired:
集合x是:
(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)
集合y(潜在答案)是:
The set y (potential answers)is :
{(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)}
,正确的答案是:
S1={(a,b),(c,d)}
S2={(a,c),(b,d)}
S3={(a,d),(b,c)}
仅当n小时才有用。
例如:
The mentioned algorithm is useful only when n is small. For instance when:
n=90, l=3 =>
|x|=117480
|y|=1.28827732e+318
and the number of correct answers is `2.533601e+82`.
因此,由于时间性能和内存问题,该算法在大多数情况下不实用。
So the algorithm is not practical for the most case due to time performance and memory issues.
由于结果数量很多,即使拥有并运行有效的算法也很耗时。例如,在上述问题中,答案的数量= 2.533601e + 82
Even having and running an efficient algorithm would be time consuming as the number of results is a lot. For instance in the above problem the number of answers = 2.533601e+82
我不是该领域的专家理论,所以也许这是一个众所周知的问题。
I am not expertise in the set theory so maybe it is a well known problem.
感谢您的帮助。
推荐答案
我想这可能很近...希望您使用的是Java
I think this might be close...hope you're using 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)
这篇关于将集合的分区枚举为大小相等的子集的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!