一组内所有对的组合

我想计算你可以组成一个集合的所有可能的对列表。例如：

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类没问题:)

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

Edit:我已经看过所有答案。现在我有了工作代码，谢谢。但我需要将它用于具有大小的输入n = 26:(。我还没有实现一切，但我想它会运行一段时间:(。

如果我理解正确的话，这个问题的递归解决方案应该相当简单：

• 从集合中删除第一个元素 A
• For each remaining element 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);
        }
    }
}