從n返回k個元素的所有組合的算法我想寫一個函數，它將一個字母數組作為參數，并選擇一些字母。假設您提供了8個字母的數組，并希望從中選擇3個字母。然后你應該得到：8! / ((8 - 3)! * 3!) = 56數組（或單詞）返回，每個包含3個字母。
4 回答
慕后森
TA貢獻1802條經驗 獲得超5個贊
計算機編程藝術第4卷：分冊3有很多這些可能比我描述的更適合你的特殊情況。
格雷碼
你會遇到的一個問題當然是記憶而且非?？?，你的組中有20個元素會出現問題 - 20 C 3 = 1140.如果你想迭代這個集合，最好使用修改后的灰色代碼算法，所以你沒有把所有這些都保存在內存中。這些產生了前一個的下一個組合，避免重復。其中有許多用于不同的用途。我們是否希望最大化連續組合之間的差異？最小化？等等。
一些描述格雷碼的原始論文：
以下是一些涉及該主題的其他文章：
Eades，Hickey，讀取相鄰交換組合生成算法的有效實現（PDF，代碼為Pascal）
組合灰度代碼調查（PostScript）
Chase's Twiddle（算法）
Phillip J Chase，“ 算法382：N個物體中M的組合 ”（1970）
C中的算法 ...
字典順序中的組合索引（帶扣算法515）
您還可以通過其索引（按字典順序）引用組合。根據索引意識到索引應該是從右到左的一些變化，我們可以構造一些應該恢復組合的東西。
所以，我們有一套{1,2,3,4,5,6} ......我們需要三個元素。讓我們說{1,2,3}我們可以說元素之間的差異是一個，有序和最小。{1,2,4}有一個變化，按字典順序排列第2位。因此，最后一個地方的“變化”數量占字典順序的一個變化。第二個位置，只有一個變化{1,3,4}有一個變化，但由于它位于第二位（與原始集合中的元素數量成比例），因此會有更多變化。
我所描述的方法是解構，似乎從設置到索引，我們需要反向 - 這更加棘手。這就是Buckles如何解決這個問題。我寫了一些C來計算它們，只需稍作修改 - 我使用集合的索引而不是數字范圍來表示集合，所以我們總是從0 ... n開始工作。注意：
由于組合是無序的，{1,3,2} = {1,2,3} - 我們將它們命名為詞典。
此方法具有隱式0以啟動第一個差異的集合。
字典順序中的組合索引（McCaffrey）
還有另外一種方法：它的概念更易于掌握和編程，但它沒有Buckles的優化。幸運的是，它也不會產生重復的組合：
最大化的集合
在哪里
舉個例子：27 = C(6,4) + C(5,3) + C(2,2) + C(1,1)。因此，第四十七個詞典組合的四個事物是：{1,2,5,6}，這些是你想要看的任何集合的索引。下面的示例（OCaml）需要choose功能，留給讀者：
(* this will find the [x] combination of a [set] list when taking [k] elements *)let combination_maccaffery set k x = (* maximize function -- maximize a that is aCb *) (* return largest c where c < i and choose(c,i) <= z *) let rec maximize a b x = if (choose a b ) <= x then a else maximize (a-1) b x in let rec iterate n x i = match i with | 0 -> [] | i -> let max = maximize n i x in max :: iterate n (x - (choose max i)) (i-1) in if x < 0 then failwith "errors" else let idxs = iterate (List.length set) x k in List.map (List.nth set) (List.sort (-) idxs)
一個小而簡單的組合迭代器
提供以下兩種算法用于教學目的。它們實現了迭代器和（更一般的）文件夾整體組合。它們盡可能快，具有復雜度O（n C k）。內存消耗受到約束k。
我們將從迭代器開始，它將為每個組合調用用戶提供的函數
let iter_combs n k f = let rec iter v s j = if j = k then f v else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in iter [] 0 0
更通用的版本將從初始狀態開始調用用戶提供的函數以及狀態變量。因為我們需要在不同狀態之間傳遞狀態，所以我們不會使用for循環，而是使用遞歸，
let fold_combs n k f x = let rec loop i s c x = if i < n then loop (i+1) s c @@ let c = i::c and s = s + 1 and i = i + 1 in if s < k then loop i s c x else f c x else x in loop 0 0 [] x
開滿天機
TA貢獻1786條經驗 獲得超13個贊
在C＃中：
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
return k == 0 ? new[] { new T[0] } :
elements.SelectMany((e, i) =>
elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}
用法：
var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);
結果：
123
124
125
134
135
145
234
235
245
345
陪伴而非守候
TA貢獻1757條經驗 獲得超8個贊
短java解決方案：
import java.util.Arrays;
public class Combination {
public static void main(String[] args){
String[] arr = {"A","B","C","D","E","F"};
combinations2(arr, 3, 0, new String[3]);
}
static void combinations2(String[] arr, int len, int startPosition, String[] result){
if (len == 0){
System.out.println(Arrays.toString(result));
return;
}
for (int i = startPosition; i <= arr.length-len; i++){
result[result.length - len] = arr[i];
combinations2(arr, len-1, i+1, result);
}
}
}
結果將是
[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]
蕪湖不蕪
TA貢獻1796條經驗 獲得超7個贊
我可以提出我的遞歸Python解決方案來解決這個問題嗎？
def choose_iter(elements, length):
for i in xrange(len(elements)):
if length == 1:
yield (elements[i],)
else:
for next in choose_iter(elements[i+1:len(elements)], length-1):
yield (elements[i],) + next
def choose(l, k):
return list(choose_iter(l, k))
用法示例：
>>> len(list(choose_iter("abcdefgh",3)))
56
我喜歡它的簡單性。
添加回答
舉報
0/150
提交
取消