第N个组合（{a，b} = {b，a}）无重复（枚举/蛮力） [英] Nth combinations ({a, b} = {b, a}) without repetition (enumeration / brute force)

问题描述

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

I'm looking for an algorithm that generates the nth combinations without repetition.

我可以在（a， b）！=（b，a），但是我正在寻找 {a，b} = {b，a} 的组合。

I could find a lot on permutations where (a, b) != (b, a), but I'm looking for combinations where {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的通用递归实现会很棒。我还要感谢一个链接，上面有很好的解释，伪代码或示例代码。

A generic, recursive implementation in Java that takes a Set or List would be great. I would also appreciate a link with a good explanation, pseudo or example code.

推荐答案

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

You can do this using the following recursive method:

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 。

---

The program works as follows: k is the number of elements we still have to pick, and i is the current offset value. Initially that offset value is 0.

现在，我们从 i 到 nk 寻找潜在的候选人。该范围内的每个元素将成为某些组合的开头。我们对列表的其余部分执行递归。递归将生成所有在列表其余部分上包含 k-1 个元素的列表。然后，我们的工作就是简单地在列表中添加一个头像，然后返回列表。

Now we iterate from i to n-k looking for potential candidates to be part of the head. Each element in that range will be the head for some combinations. We perform recursion on the remainder of the list. The recursion generates all the lists that take k-1 elements on the remainder of the list. Then our job is simply to add a head in front and return the list.

您可以通过使用特殊的<$ c来更快，更保守地实现此功能。 $ c> LinkedList （这在逻辑和函数编程语言中很常见）。

You can implement this both faster and more memory conservative by using a special form of LinkedLists (which are common in logic and functional programming languages).

这篇关于第N个组合（{a，b} = {b，a}）无重复（枚举/蛮力）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！