TA貢獻(xiàn)1802條經(jīng)驗 獲得超5個贊
計算機(jī)編程藝術(shù)第4卷：分冊3有很多這些可能比我描述的更適合你的特殊情況。
你會遇到的一個問題當(dāng)然是記憶而且非常快，你的組中有20個元素會出現(xiàn)問題 - 20 C 3 = 1140.如果你想迭代這個集合，最好使用修改后的灰色代碼算法，所以你沒有把所有這些都保存在內(nèi)存中。這些產(chǎn)生了前一個的下一個組合，避免重復(fù)。其中有許多用于不同的用途。我們是否希望最大化連續(xù)組合之間的差異？最小化？等等。
一些描述格雷碼的原始論文：
以下是一些涉及該主題的其他文章：
Eades，Hickey，讀取相鄰交換組合生成算法的有效實現(xiàn)（PDF，代碼為Pascal）
組合灰度代碼調(diào)查（PostScript）
Phillip J Chase，“ 算法382：N個物體中M的組合 ”（1970）
C中的算法 ...
您還可以通過其索引（按字典順序）引用組合。根據(jù)索引意識到索引應(yīng)該是從右到左的一些變化，我們可以構(gòu)造一些應(yīng)該恢復(fù)組合的東西。
所以，我們有一套{1,2,3,4,5,6} ......我們需要三個元素。讓我們說{1,2,3}我們可以說元素之間的差異是一個，有序和最小。{1,2,4}有一個變化，按字典順序排列第2位。因此，最后一個地方的“變化”數(shù)量占字典順序的一個變化。第二個位置，只有一個變化{1,3,4}有一個變化，但由于它位于第二位（與原始集合中的元素數(shù)量成比例），因此會有更多變化。
我所描述的方法是解構(gòu)，似乎從設(shè)置到索引，我們需要反向 - 這更加棘手。這就是Buckles如何解決這個問題。我寫了一些C來計算它們，只需稍作修改 - 我使用集合的索引而不是數(shù)字范圍來表示集合，所以我們總是從0 ... n開始工作。注意：
由于組合是無序的，{1,3,2} = {1,2,3} - 我們將它們命名為詞典。
此方法具有隱式0以啟動第一個差異的集合。
還有另外一種方法：它的概念更易于掌握和編程，但它沒有Buckles的優(yōu)化。幸運(yùn)的是，它也不會產(chǎn)生重復(fù)的組合：
最大化的集合
在哪里
舉個例子：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)
提供以下兩種算法用于教學(xué)目的。它們實現(xiàn)了迭代器和（更一般的）文件夾整體組合。它們盡可能快，具有復(fù)雜度O（n C k）。內(nèi)存消耗受到約束k。
我們將從迭代器開始，它將為每個組合調(diào)用用戶提供的函數(shù)
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
更通用的版本將從初始狀態(tài)開始調(diào)用用戶提供的函數(shù)以及狀態(tài)變量。因為我們需要在不同狀態(tài)之間傳遞狀態(tài)，所以我們不會使用for循環(huán)，而是使用遞歸，
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貢獻(xiàn)1786條經(jīng)驗 獲得超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);
結(jié)果：
123
124
125
134
135
145
234
235
245
345
TA貢獻(xiàn)1757條經(jīng)驗 獲得超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);
}
}
}
結(jié)果將是
[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貢獻(xiàn)1796條經(jīng)驗 獲得超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
我喜歡它的簡單性。
舉報