第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的通用递归实现会很棒。我也希望链接提供很好的解释，伪代码或示例代码。

Answer 1

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

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个 元素的列表。然后，我们的工作只是简单地在前面添加一个头并返回列表。

通过使用特殊形式的LinkedLists（在逻辑和函数编程语言中很常见），可以更快地实现此目标，并且可以使存储保守性更高。