Tutorial of finding all the C(n, m) combinations of an array

Combations.md

#組合

如何找出 C(N, M) （C N 取 M）的所有組合，我們的工具有 next_permutation ，但它只能用來做排列，所以我們需要一點小技巧。

考慮資料是 [4, 3, 6, 2, 1] 。我們想找出 C(5, 2) 的所有組合，我們可以設一個長度為 5 的零一陣列，其中前三項為 0 ，後二項為 1：

[0, 0, 0, 1, 1]

接著我們對這個陣列排列，得到結果如下：

0, 0, 0, 1, 1 
0, 0, 1, 0, 1 
0, 0, 1, 1, 0 
0, 1, 0, 0, 1 
0, 1, 0, 1, 0 
0, 1, 1, 0, 0 
1, 0, 0, 0, 1 
1, 0, 0, 1, 0 
1, 0, 1, 0, 0 
1, 1, 0, 0, 0

我們將這些排列對應到資料 [4, 3, 6, 2, 1] ，一個位置對一個一位置，當排列中那個位置的值是 1 的時候，我們就把資料中對應的那一項拿出來。

例如，排列是 0, 1, 0, 0, 1 時，我們就是把資料中的第 1 項（3），跟第 4 項 （1）拿出來，組成一個新的長度為 2 的陣列，這個陣列就是 C(5, 2) 中的一個組合。

idx	0	1	2	3	4
flag	0	1	0	0	1
data	4	3	6	2	1

=> [3, 1]

---

也許你在期末 project 中可能不會用到，但建議還是把這個方法學起來，這個方法極為高效，比起你對整個資料排列，然取前 M 項的方法快許多了。

---

完整程式碼：

#include <stdio.h>

int next_permutation(int *array, int length) {
	int i, j;
	int temp;
	
	// Find non-increasing suffix
	if (length == 0)
		return 0;
	i = length - 1;
	while (i > 0 && array[i - 1] >= array[i])
		i--;
	if (i == 0)
		return 0;
	
	// Find successor to pivot
	j = length - 1;
	while (array[j] <= array[i - 1])
		j--;
	temp = array[i - 1];
	array[i - 1] = array[j];
	array[j] = temp;
	
	// Reverse suffix
	j = length - 1;
	while (i < j) {
		temp = array[i];
		array[i] = array[j];
		array[j] = temp;
		i++;
		j--;
	}
	
	return 1;
}

int main(void) {
	int data[5] = {4, 3, 6, 2, 1};
	
	int flag[5] = {0, 0, 0, 1, 1};
	
	do {
		int i;
		
		int comb[2];
		int comb_idx = 0;
		for (i=0; i<5; i++)
			if (flag[i] == 1)
				comb[comb_idx++] = data[i];
		
		printf("flag: ");
		for(i=0; i<5; i++)
			printf("%d, ", flag[i]);
		
		printf("comb: ");
		for (i=0; i<2; i++)
			printf("%d ", comb[i]);
		printf("\n");
	} while (next_permutation(flag, 5));
	
	return 0;
}

執行結果：

flag: 0, 0, 0, 1, 1, comb: 2 1 
flag: 0, 0, 1, 0, 1, comb: 6 1 
flag: 0, 0, 1, 1, 0, comb: 6 2 
flag: 0, 1, 0, 0, 1, comb: 3 1 
flag: 0, 1, 0, 1, 0, comb: 3 2 
flag: 0, 1, 1, 0, 0, comb: 3 6 
flag: 1, 0, 0, 0, 1, comb: 4 1 
flag: 1, 0, 0, 1, 0, comb: 4 2 
flag: 1, 0, 1, 0, 0, comb: 4 6 
flag: 1, 1, 0, 0, 0, comb: 4 3