一组内所有对的组合 [英] All combinations of pairs within one set

问题描述

我想计算你可以制作一组的所有可能的对列表。例如：

I want to compute all possible lists of pairs you could make of a set. For instance:

intput = [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)],
          [...], .... }

注意：这个例子只是输出中的一些随机内容，大多数都被删除了。我不关心列表的顺序或这些列表中的对。

Note: this example are just some random things in the output, most is removed. I don't care about the order of the lists or the pairs within those lists.

我认为会有（n-1）（n-3）（n-5）... 可能的对名单。首先，我强调你可以输入输入列表的所有排列。通过所有这些排列，您可以将第一个与第二个项目分组，第三个与第四个组合。但显然这是非常低效的，因为你会在列表中制作 n！项目，你只需要（n-1）（n-3） ）（N-5）... 。有些人可以给我一个如何提高效率的提示。是否有已知算法或搜索适当的关键字。我想在JAVA中实现它，所以如果你想在JAVA中使用Collections类没问题：）

I think there would be (n-1)(n-3)(n-5)... possible lists of pairs. First I tough you could make all permutations of the input list. With all those permutations you could group the first with the second item and the third with fourth. But obviously that is very inefficient, because you would make n! items in the list and you would only need (n-1)(n-3)(n-5).... Could some give me a hint how to do this more efficient. Is there a known algorithm or what would the proper keywords to search with. I want to implement this in JAVA, so if you want to make use of the Collections class in JAVA no problem :)

更清楚：输入总是包含偶数个元素，因此一个列表中的所有对都是输入中的所有元素。

To be more clear: the input always consist of a even number of elements so all pairs in one list together are all elements in the input.

编辑：
我看到了所有答案。现在我有工作代码，谢谢你。但我需要使用它来输入大小 n = 26 :(。我还没有实现所有内容，但我想它会运行一段时间:(。

I have look to all answer. Now I have working code thanks for that. But I need to use it for a input with size n = 26 :(. I have not implemented everything yet, but I guess it's going to run for a while :(.

推荐答案

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

If I understood this correctly, a recursive solution to this problem should be rather simple:

• 从集合中移除第一个元素A


• 对于每个剩余元素B：
  
  
  
  • 从集合中删除元素B
  
  
  • 创建一对（A，B）并将其存储为当前解决方案的一部分
  
  
  • 执行使用剩余设置进行递归。这将为当前解决方案添加更多对。如果集合中没有剩余元素，则将当前解决方案存储为最终解决方案之一。
  
  
  • 将元素B添加到集合
  
  
  • Remove the first element A from the set
  • For each remaining element B:
    • Remove element B from the set
    • Create a pair (A,B) and store it as part of the current solution
    • Do the recursion with the remaining set. This will add more pairs to the current solution. If there are no more elements left in the set, then store the current solution as one of the final solutions.
    • Add element B to the set

    添加和删除元素的部分实际上并不包含在此示例实现中，因为它创建了es一个列表和一个新的迭代和递归调用集，但想法应该是明确的。

    The part with adding and removing the elements is not really contained in this example implementation, because it creates a list and a new set for the iteration and the recursive call, but the idea should be clear.

    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);
            }
        }
    }
    

    这篇关于一组内所有对的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！