我想计算您可以组成一组的所有可能的配对列表。例如:
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
:(。的输入中。我还没有实现所有功能,但是我想它会运行一段时间了:(。
如果我正确理解这一点,那么对这个问题的递归解决方案应该很简单:
此示例实现中并未真正包含添加和删除元素的部分,因为它为迭代和递归调用创建了一个列表和一个新集合,但是这个主意应该很清楚。
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);
}
}
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句