如果项目只能在一个组合中出现一次，则生成组合

Question

假设我有N项。现在我想创建M项组合，但如果已经存在一个组合{a,B,C}(在这种情况下M=3)，那么a不能与B或C一起出现在另一个组合中。

示例:N={1,2,3,4,5,6,7,8,9,10}， M=3，则可能的组合应为:

• {1,2,3}
• {4、5、6}
• {7 8 9}
• {10,1,2} -这不是一个有效的组合，因为1和2已经在生成的组合{1,2,3}
• {10 1 4}
• {2,5,8} -有效，因为所有项目总是以不同的组合
• …

我可以创建多少个组合?

我如何系统地生成这样的组合?

如果我允许两个项以两种不同的组合在一起会怎样?因此，组合{1,2,3}和{1,2,4}将是有效的。

Answer 1

蛮力，但相当快。在python，但明确的方法，我相信:

from itertools import combinations as c
data = range(1,11)
already_seen = set()
result = set()
all_combos = c(data,3)
for combo in all_combos:
pairs = set(c(combo, 2))
if not pairs & already_seen:
result.add(combo)
already_seen.update(pairs)
print(result)
# {(3, 9, 10), (3, 5, 6), (1, 2, 3), (2, 8, 10), (1, 4, 5), (2, 5, 7), (2, 4, 6), (1, 8, 9), (1, 6, 7), (3, 4, 7)}

Answer 2

我想你可以使用标准的组合生成算法，只需添加使用对的验证，就像这样(在java中，但很清楚如何移植到任何其他语言):

import java.util.*;
public class Test {
public static void main(String[] args) {
generateCombinations(3, 10);
}
public static void generateCombinations(int m, int n) {
var used = new HashSet<Long>();
var combination = new HashSet<Integer>();
for (int i = 1; i <= n; i++) generateCombination(i, m, n, used, combination);
}
public static boolean generateCombination(int c, int m, int n, Set<Long> used, Set<Integer> comb) {
for (Integer ci : comb) if (used.contains(getPair(ci.intValue(), c))) return false;
boolean result = false;
for (Integer ci : comb) used.add(getPair(ci.intValue(), c));
comb.add(c);
if (comb.size() < m) {
for (int i = c + 1; i <= n; i++) {
result |= generateCombination(i, m, n, used, comb);
if (result && comb.size() >= 2) break;
}
} else {
result = true;
System.out.println(Arrays.toString(comb.toArray(new Integer[comb.size()])));
}
comb.remove(c);
if (!result) for (Integer ci : comb) used.remove(getPair(ci.intValue(), c));
return result;
}
public static long getPair(int a, int b) {
return (((long) a) << 32L) | b;
}
}

对于3-10，它生成10个组合，我想这是子集的最大数量，请随意证明我错了

[1, 2, 3]
[1, 4, 5]
[1, 6, 7]
[1, 8, 9]
[2, 4, 6]
[2, 5, 7]
[2, 8, 10]
[3, 4, 7]
[3, 5, 6]
[3, 9, 10]

扩展它应该是比较容易的，以支持唯一的三元组而不是对，只是生成字符串键像min(a,b,c) + "_" + middle(a,b,c) + "_" + max(a,b,c)而不是按位hack我曾经加速并添加所有从comb集到used集