星期五, 4月 06, 2012

求出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也能正常編譯執行.

沒有留言: