一、概念
什麼是組合數呢？
從m個不同元素中取出n（n≤m）個元素的所有組合的個數，叫做從m個不同元素中取出n個元素的組合數（Combination）。
組合數基本公式為：
Cnm=m!n!(m−n)!
線性寫法為：c(m,n) = m!/((m-n)!*n!)
現實生活中彩票的機率計算就涉及到組合數，比如雙色球中紅球選擇需要從
01~33
紅球中選出6個，組合結果為 c(33,6) = 1107568.
二、計算方式
由于計算機資料存儲方式的限制，階乘的計算，如果是long int型隻能正确計算到12左右的階乘，如果用double型隻能正确計算170左右的階乘，當然這些隻是大概，需要結合實際平台進行驗證。
是以采用階乘計算稍大數組合數是不合适的，而且效率不高，但是可以先對公式進行轉換然後再進行計算：
1.對公式兩邊取自然對數
ln(Cnm)=ln(m!n!(m−n)!)
2.根據對數性質進行轉換
ln(Cnm)=ln(m!)−ln(n!)−ln((m−n)!)
ln(Cnm)=∑i=1mln(i)−∑i=1nln(i)−∑i=1m−nln(i)
-
由于
∑i=1mln(i)=∑i=1nln(i)+∑i=n+1mln(i)
-
去除相同項
ln(Cnm)=∑i=n+1mln(i)−∑i=1m−nln(i)
-
到這就已經将階乘轉換成對數連加，極大的降低了運算的複雜度。另外，依據組合數性質：
Cnm=Cm−nm
當 n > m/2 時，n 相對于 m - n 是一個較大的數，此時可以取 n = m - n進行計算。
3.進行計算
以第2步得到的公式計算出
ln(Cnm)
的值，然後再取反對數就可以得到組合數結果了。
用這種方法計算組合數，如果隻計算ln(C(m,n))的話，n可以取到整型資料的極限值65535，
ln(C(65535,32767)) = 45419.6
而計算時間可以達到毫秒級。當然，如果要取反對數得到最終的組合數的話，m的取值就不能達到這麼大了，但是這種算法仍然可以保證m取到1000以上。
4.該算法OC實作代碼
/**
組合數計算
@param totalNum C(m,n) 中 m
@param requireNum C(m,n) 中 n
@return 組合數結果
*/
+ (NSInteger)selectFromTotalNum:(NSInteger)totalNum requireNum:(NSInteger)requireNum{
if (totalNum < requireNum) {
return ;
}
if (requireNum < totalNum / ) {
requireNum = totalNum - requireNum;
}
double s1 = ;
for (NSInteger i = requireNum + ; i <= totalNum; i ++) {
s1 += log((double)i);
}
double s2 = ;
NSInteger ub = totalNum - requireNum;
for (int i = ; i <= ub; i++) {
s2 += log((double)i);
}
double result = exp(s1 - s2);
//此處需要先進行四舍五入，不能直接強行取整，不然可能會有 1 的誤內插補點
double temp = round(result); //四舍五入
return (NSInteger)temp;
}
三、擷取所有的可能組合
所有的可能性組合可以通過排列組合獲得，該方式計算耗時長、資源占用嚴重，在iPhone6上測試僅 C(33,16) 的計算就需 12s左右的時間，記憶體和cpu更是爆滿，但是當 m <= 10 時 還是可以接受的，是以該方法具有很大的局限性。
-
方法原理
從包含m個元素的數組中不計順序的選出n個元素，
思路是建立一個數組，下标表示1到m個數，數組元素的值為1表示其下标代表的數被選中，為0則沒選中。
首先初始化，将數組前n個元素置1，表示第一個組合為前n個數。
然後周遊數組元素值的 1、0 組合，找到第一個 1、0 組合後将其變為 0、1 組合，
同時将其左邊的所有“1”全部移動到數組的最左端。
當第一個“1”移動到數組的m-n的位置，即n個“1”全部移動到最右端時，就得到了最後一個組合。
例如求5中選3的組合：
//1,2,3 //1,2,4 //1,3,4 //2,3,4 //1,2,5 //1,3,5 //2,3,5 //1,4,5 //2,4,5 //3,4,5 - 實作代碼(oc)
+ (NSArray *)selectFromSource:(NSArray *)source requireNum:(int)requireNum{
NSMutableArray *results = [NSMutableArray array]; //排列組合結果
//@1 表示選中，@0 表示未選中
NSMutableArray *arr = [NSMutableArray array];
NSMutableArray *firstItem = [NSMutableArray array];
for (int i = ; i < source.count; i ++) {
if (i < requireNum) {
[arr addObject:@1];
[firstItem addObject:source[i]];
}else{
[arr addObject:@0];
}
}
//第一種排列組合結果就是選擇前 chooseNum 個元素
[results addObject:firstItem];
while () {
for (int index = ; index < arr.count; index ++)
{
//排列組合完畢時退出循環
NSArray *checkArr = [arr objectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(, source.count - requireNum)]];
if (![checkArr containsObject:@1])
{
return results;
}
if ((index < source.count - ) && [arr[index] isEqual:@1] && [arr[index + ] isEqual:@0])
{
[arr exchangeObjectAtIndex:index withObjectAtIndex:index + ];
NSMutableArray *tempArr = [NSMutableArray arrayWithArray:[arr objectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(, index)]]];
//将index左側元素拿出來，并将其中所有的 移至左側，這裡可以使用系統的排序方法
[tempArr sortUsingComparator:^NSComparisonResult(NSNumber * obj1, NSNumber * obj2) {
return [obj1 intValue] < [obj2 intValue];
}];
//替換arr中 index 左側元素
[arr replaceObjectsInRange:NSMakeRange(, index) withObjectsFromArray:tempArr];
//将已選擇的元素挑選出來儲存
NSMutableArray *selectedArr = [NSMutableArray array];
for (int j = ; j < arr.count; j ++)
{
if ([arr[j] isEqual:@1]) {
[selectedArr addObject:source[j]];
}
}
[results addObject:[selectedArr mutableCopy]];
break;
}
}
}
}
參考文章：
1.高效的組合數計算方法
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)