我想弄清楚所有不同的方式,我可以使用objective-c从6个对象创建4组。我需要什么样的算法?
例如,如果我有下列对象:A,B,C,d,E,F
然后,我可以创建组像
A,B,C,d
b,C,d,E
一个,d,E,F
等。顺序无关紧要。如果我想弄清楚所有不同的可能性,我需要什么样的算法?起初我正在考虑排列组合,但我不认为就是这样。我认为可能有更快或更合适的东西,但我忘记了它的名字。
我想弄清楚所有不同的方式,我可以使用objective-c从6个对象创建4组。我需要什么样的算法?
例如,如果我有下列对象:A,B,C,d,E,F
然后,我可以创建组像
A,B,C,d
b,C,d,E
一个,d,E,F
等。顺序无关紧要。如果我想弄清楚所有不同的可能性,我需要什么样的算法?起初我正在考虑排列组合,但我不认为就是这样。我认为可能有更快或更合适的东西,但我忘记了它的名字。
如果您需要以各种可能的方式选择4个不同的对象,这意味着您需要以各种可能的方式移除('不选择')两个其他对象。只有两个循环:
for (int i = 0; i < 6; ++i) {
for (int j = i + 1; j < 6; ++j) {
// here we select all elements except i and j
}
}
如果对象数量增加,但不够容易扩展,但足够简单。
(我假设顺序并不重要:它从你的例子似乎如此)
对,顺序无关紧要。 – 2010-09-25 04:21:24
置换启动正确的地方。一个暴力方法是找到所有的六个字符串排列,只需抓住前四个并将它们添加到一个集合中。尽管效率非常低下。
可以调整基本置换算法来生成四个组。
看看这个页面:http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
这里是一个递归方法,用Java编写的,适用于一般情况下:
public static void comb(int[] arr, int m) {
comb(arr, m, 0, new ArrayList<Integer>());
}
public static void comb(int[] arr, int m, int ind, ArrayList<Integer> s) {
int left = m - s.size();
if (left == 0) {
System.out.println(s);
return;
}
if (left > arr.length - ind)
return;
comb(arr, m, ind + 1, s);
s.add(arr[ind]);
comb(arr, m, ind + 1, s);
s.remove(s.size()-1);
}
它每次找到一个项目,需要决定是否时间分支包括它或不包括。还有一个修剪优化可以避免死角。
如果选择内的排序不重要,则需要组合。请参阅:http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n – 2010-09-25 04:18:10
请检查常见问题解答:http://stackoverflow.com/tags/algorithm/faq – 2010-09-25 13:38:10