跳到主要內容

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

留言

這個網誌中的熱門文章

自然人憑證讀卡機驅動程式

鳥毅用的是第一代的自然人憑證讀卡機,EZ100PU(後來有同事買EZmini可以讀SIM卡似乎更好),每年報稅時用一次。 本來只是要申請些政府業務,一時之間找不到光碟,沒想到在 驅動程式下載 居然看到Linux和Mac的驅動程式,剩下的就是政府單位的網頁和程式應該改版了吧!!!

在Windows Server設定L2TP over IPSec VPN

簡單地說,macOS Sierra與iOS 10發表後,大家忽然發現Apple不再支援PPTP,所以一定得設定其他的VPN型態。若不要另外裝client,用L2TP是最方便的,SSL VPN雖然好,但若沒有安裝Agent要連線到任一電腦或是非網頁服務還是挺麻煩的。