生成组合如果物品只能组合一次

Question

假设我有n个项目。 3），那么a不能与b nor C一起使用。

现在，我想创建m-item组合，但是如果已经存在组合{a，b，c}（在这种情况下为m = 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,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中）（在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，a， b，c） +“ _” + max（a，b，c）而不是位于comb 设置为使用的使用设置