一组内所有对的组合

Question

我想计算一个集合中所有可能的配对列表。例如：

input = [1, 2, 3, 4, 5, 6]

output = {[(1,2), (3,4), (5,6)],
          [(2,3), (4,5), (1,6)],
          [(2,4), (1,3), (5,6)],
          [...], .... }

注意：本示例只是输出中的一些随机内容，大部分已删除。我不在乎列表的顺序或这些列表中的对。

我认为可能会有(n-1)(n-3)(n-5)...成对的清单。首先，我认为您可以对输入列表进行所有排列。通过所有这些排列，您可以将第一项与第二项组合在一起，将第三项与第四项组合在一起。但这显然效率很低，因为您可以n!在列表中制造商品，而您只需要(n-1)(n-3)(n-5)...。有人可以给我提示如何更有效地执行此操作吗？是否存在已知的算法，或者将使用适当的关键字进行搜索？我想在JAVA中实现此功能，因此，如果您想在JAVA中使用Collections类，没问题:)

更明确地说：输入始终由偶数个元素组成，因此一个列表中的所有对在一起都是输入中的所有元素。

编辑： 我期待所有答案。现在我有了工作代码，对此表示感谢。但是我需要将它用于大小为n = 26:(。的输入中。我还没有实现所有功能，但是我想它会运行一段时间了:(。

Answer 1

如果我正确理解这一点，那么对这个问题的递归解决方案应该很简单：

• 从集合中删除第一个元素A
• 对于每个剩余的元素B：
  • 从集合中删除元素B
  • 创建一个对（A，B）并将其存储为当前解决方案的一部分
  • 对其余的集合进行递归。这将为当前解决方案添加更多对。如果集合中没有剩余元素，则将当前解决方案存储为最终解决方案之一。
  • 将元素B添加到集合中
• 将元素A添加到集合中

此示例实现中并未真正包含添加和删除元素的部分，因为它为迭代和递归调用创建了一个列表和一个新集合，但是这个主意应该很清楚。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class AllPairs
{
    public static void main(String[] args)
    {
        Set<Integer> set = new LinkedHashSet<Integer>(
            Arrays.asList(1,2,3,4,5,6));

        ArrayList<List<List<Integer>>> results = 
            new ArrayList<List<List<Integer>>>();
        compute(set, new ArrayList<List<Integer>>(), results);
        for (List<List<Integer>> result : results)
        {
            System.out.println(result);
        }
    }

    private static void compute(Set<Integer> set,
        List<List<Integer>> currentResults,
        List<List<List<Integer>>> results)
    {
        if (set.size() < 2)
        {
            results.add(new ArrayList<List<Integer>>(currentResults));
            return;
        }
        List<Integer> list = new ArrayList<Integer>(set);
        Integer first = list.remove(0);
        for (int i=0; i<list.size(); i++)
        {
            Integer second = list.get(i);
            Set<Integer> nextSet = new LinkedHashSet<Integer>(list);
            nextSet.remove(second);

            List<Integer> pair = Arrays.asList(first, second);
            currentResults.add(pair);
            compute(nextSet, currentResults, results);
            currentResults.remove(pair);
        }
    }
}