我需要什麼樣的算法？

我想弄清楚所有不同的方式，我可以使用objective-c從6個對象創建4組。我需要什麼樣的算法？

例如，如果我有下列對象：A，B，C，d，E，F

然後，我可以創建組像

A，B，C，d

b，C，d，E

一個，d，E，F

等。順序無關緊要。如果我想弄清楚所有不同的可能性，我需要什麼樣的算法？起初我正在考慮排列組合，但我不認爲就是這樣。我認爲可能有更快或更合適的東西，但我忘記了它的名字。

來源

2010-09-25 node ninja

如果選擇內的排序不重要，則需要組合。請參閱：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

如果您需要以各種可能的方式選擇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:16:46

對，順序無關緊要。 – 2010-09-25 04:21:24

置換啓動正確的地方。一個暴力方法是找到所有的六個字符串排列，只需抓住前四個並將它們添加到一個集合中。儘管效率非常低下。

可以調整基本置換算法來生成四個組。

看看這個頁面：http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

來源

2010-09-25 04:18:28 JoshD

這裏是一個遞歸方法，用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); 
}

它每次找到一個項目，需要決定是否時間分支包括它或不包括。還有一個修剪優化可以避免死角。

來源

2010-09-25 15:47:01

我需要什麼樣的算法？

回答

相關問題