第 N 次组合 ({a, b} = {b, a}) 无重复（枚举/蛮力）

Question

我正在寻找一种可以生成第 n 个组合而不重复的算法。

我可以找到很多关于 (a, b) != (b, a) 的排列，但我正在寻找 {a, b} = {b, a}.

的组合

示例：

Set = {a, b, c}
n = 2
Combinations: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}

Java 中采用 Set 或 List 的通用递归实现会很棒。我也希望 link 有很好的解释、伪代码或示例代码。

Answer 1

递归算法很简单：

删除第一个元素。
将它与列表中的其他元素配对
将该列表添加到由其余元素创建的列表中

Answer 2

您可以使用以下递归方法执行此操作：

public static<T> ArrayList<ArrayList<T>> getPermutations (List<T> elements, int k) {
    return getPermutations (elements,k,0);
}

public static<T> ArrayList<ArrayList<T>> getPermutations (List<T> elements, int k, int i) {
    ArrayList<ArrayList<T>> results = new ArrayList<>();
    if(k > 0) {
        int n = elements.size();
        for(int j = i; j <= n-k; j++) {
            T val = elements.get(j);
            ArrayList<ArrayList<T>> tails = getPermutations(elements,k-1,j+1);
            for(ArrayList<T> tail : tails) {
                ArrayList<T> result = new ArrayList<>();
                result.add(val);
                result.addAll(tail);
                results.add(result);
            }
        }
    } else {
        results.add(new ArrayList<T>());
    }
    return results;
}

然后您可以运行例如 (jDoodle):

ArrayList<Character> set = new ArrayList<>();
set.add('a');
set.add('b');
set.add('c');

for(ArrayList<Character> element : getPermutations(set,2)) {
    System.out.println(element);
}
System.out.println("----------");
for(ArrayList<Character> element : getPermutations(set,3)) {
    System.out.println(element);
}
System.out.println("----------");

set.add('d');

for(ArrayList<Character> element : getPermutations(set,2)) {
    System.out.println(element);
}
System.out.println("----------");
for(ArrayList<Character> element : getPermutations(set,3)) {
    System.out.println(element);
}

生成：

[a, b]
[a, c]
[b, c]
----------
[a, b, c]
----------
[a, b]
[a, c]
[a, d]
[b, c]
[b, d]
[c, d]
----------
[a, b, c]
[a, b, d]
[a, c, d]
[b, c, d]

程序的工作原理如下：k是我们还需要拾取的元素个数，i是当前的偏移值。最初该偏移值是 0.

现在我们从 i 迭代到 n-k 寻找潜在的候选人成为头部的一部分。该范围内的每个元素都将成为某些组合的头部。我们对列表的其余部分执行递归。递归生成所有列表，这些列表在列表的其余部分采用 k-1 个元素。那么我们的工作就是简单地在前面添加一个头部和 return 列表。

您可以通过使用一种特殊形式的 LinkedList（在逻辑和函数式编程语言中很常见）来实现这一点，既更快又更节省内存。

Answer 3

还记得找k-th permutations of the elements? Not a lot of people know the reason behind the algorithm, but it has a mathematical theory behind it. It can be solved by representing the number in factorial number system的问题吗。

如果问题是关于寻找 k 组合，我为什么要谈论 k-th 排列？只是因为它可以用类似的数学理论来解决。惊喜，惊喜，还有一个combinatorial number system:

A k-combination of a set S is a subset of S with k (distinct) elements. The main purpose of the combinatorial number system is to provide a representation, each by a single number, of all {\displaystyle {\tbinom {n}{k}}} possible k-combinations of a set S of n elements.

阅读本文，很可能您将能够解决您的问题。

Answer 4

给定输入 list 和 n，将 list 拆分为第一项，列表的其余部分称为 head 和 tail。那么，您寻求的组合是：

你可以从tail和n得到的组合，加上
您可以从 tail 和 n-1 获得的组合，每个组合都带有 head 前缀

如果n为0，结果只有一个组合：{}

如果n大于list的大小，结果是没有组合

旁注：为了好玩，我在 Haskell 中解决了这个问题，将 n = 0 的情况放在顶部：

comb 0 _ = [[]]
comb n (head:tail) | n > 0 = comb n tail ++ map (head:) (comb (n-1) tail)
comb _ _ = []

第 N 次组合 ({a, b} = {b, a}) 无重复（枚举/蛮力）

Nth combinations ({a, b} = {b, a}) without repetition (enumeration / brute force)

java

generics

algorithm

combinations

combinatorics