求出n取k組合的列表 CSharp版

同事要找出n中取k的所有組合列表，他想出了一個很簡單的表示法。例如說3取1會有3個,就表示為

001、010、100

這的確是再簡單不過，非常清楚也利於程式使用。他使用的方法是寫一個int, 用for迴圈，從1到2的n次方-1的數字跑一遍，再把每個數字的位元做比對。

但是問題來了，數字小時這樣沒什麼問題，但是他的樣本n超過int的長度，只好改用long，而且光是long就跑很久，最近遇到的問題還超過long〈超過64個〉。


本來聽他說的時候我還沒搞懂他的問題，建議他用BigInteger去處理，等到我搞懂後，覺得這應該和我前幾年寫解棋盤程式類似。

原理 ：先把第一個位元假設為0和1，再用n-1取k與n-1取k-1遞迴處理，這樣需要跑的次數非常少。

以下為C#版本，其餘版本陸續補上。

Combinations.cs

using System;
using System.Collections;

namespace Combinations
{
 public class Combinations
 {
  private ArrayList list;
  public ArrayList Calc(int all, int want)
  {
   list = new ArrayList();
   char [] fake = new char[0];
   Calc(fake, all, want);
   Console.WriteLine("Total:{0} combinations.", list.Count);
   foreach(string str in list)
   {
    Console.WriteLine(str);
   }
   return list;
  }
  void AddList (string before, string after)
  {
   list.Add(string.Format("{0}{1}",  before,  after));
  }
  
  protected void Calc(char[] before, int all, int want)
  {
   char []strAll = new char[all];
   if(want == 0)
   {
    for(int i=0; i<all;i++)
    {
     strAll[i] = '0';
    }
    AddList (new string(before),  new string(strAll));
   }
   else if(all == want) {
    for(int i=0; i<all;i++)
    {
     strAll[i] = '1';
    }
    AddList (new string(before),  new string(strAll));
   }
   else if(all == 1)
   {
    switch(want)
    {
     AddList(new string(before),  "0");
     break;
    case 1:
     AddList(new string(before),  "1");
     break;
    }
   }
   else
   {
    char [] newbefore = new char[before.Length +1];
    for(int i=0; i< before.Length; i++)
    {
     newbefore[i] = before[i];
    }
    newbefore[before.Length]='0';
    Calc (newbefore, all-1, want);
    newbefore[before.Length]='1';
    Calc (newbefore, all-1, want-1);
   }
  }
 }
}

 public class MainClass
 {
  public static void Main (string[] args)
  {
   Combinations cn = new Combinations();
   cn.Calc(5, 2);
  }
 }

執行結果：

Total:10 combinations.
00011
00101
00110
01001
01010
01100
10001
10010
10100
11000

補充說明：最近我的桌機拿去當測試Server, 所以都是在MBP上完成, 這是用MonoDevelop IDE寫出來, 用Visual Studio也能正常編譯執行.