列印出 N 個元素集合中
所有 m 個元素的子集合

在 N 個元素集合中 m 個元素的子集合共有 C(N,m) 個

3 個元素的子集合包括下列 C(5,3)=10 個：

0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

怎樣寫一個 C 程式來列印出這些子集合呢?

0 1 2  <-- 這組數字很容易可以得到

0 1 3  <-- 將上一組數字中最低位加 1，如果小於 N=5 的話就完成了

0 1 4  <-- 將上一組數字中最低位加 1，檢查小於 5，完成

0 2 3  <-- 將上一組數字中最低位加 1，發現已經等於 5，將倒數第二位數字加 1，
           將最低位數字設為倒數第二位數字加 1
           
0 2 4  <-- 將上一組數字中最低位加 1，檢查小於 5，完成

0 3 4  <-- 將上一組數字中最低位加 1，發現已經等於 5，將倒數第二位數字加 1，
           將最低位數字設為倒數第二位數字加 1，完成
           
1 2 3  <-- 將上一組數字中最低位加 1，發現已經等於 5，將倒數第二位數字加 1，
           發現已經等於 N-1=4，於是繼續往前一位數，將倒數第三位數字加 1，
           檢查是否等於 N-2=3，將其後的位數內數字順序加 1，完成
           
1 2 4  <-- 將上一組數字中最低位加 1，檢查小於 5，完成

1 3 4  <-- 將上一組數字中最低位加 1，發現已經等於 5，將倒數第二位數字加 1，
           將最低位數字設為倒數第二位數字加 1，完成
           
2 3 4  <-- 將上一組數字中最低位加 1，發現已經等於 5，將倒數第二位數字加 1，
           發現已經等於 4，於是繼續往前一位數，將倒數第三位數字加 1，
           檢查是否等於 3，將其後的位數內數字順序加 1，完成
           
3 x x  <-- 將上一組數字中最低位加 1，發現已經等於 5，將倒數第二位數字加 1，
           發現已經等於 4，於是繼續往前一位數，將倒數第三位數字加 1，
           發現已經等於 3，程式結束

程式要求：

1. 這個程式理論上也可以用遞迴 (recursive) 來做， 或是甚至把所有的子集合列出來， 然後在篩檢出 m 個元素的子集合， 但是繳交此作業時， 請務必依照上面解釋的方法來做

2. 請儘量用函式來簡化邏輯， 執行速度暫時不用太在意， 當然你可以討論一下不同的 N 值大概需要多少時間。

3. 你需要用陣列變數來記錄數字

4. 請以 ANSI C 語法及函式庫來製作

範例執行程式：

    Iterated Version [FindCombinationsIter.exe]，
    Recursive Version [FindCombinationsRecur.exe]

回 程式設計課程 首頁

製作日期: 99/10/19 by 丁培毅 (Pei-yih Ting)
E-mail: pyting@cs.ntou.edu.tw