跳到主要內容

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

為增加篇幅,今天來到functional programming,也是以求出組合為例。
有了functional的能力,加上Ruby的syntax sugar,同樣功能的code變得真少,相信真正會寫Ruby的人可以寫更少。

感謝高見龍大神的指教,先更正了原本在1.8.7會錯誤的語法,又告知Ruby有內建的排列組合指令 permutation與combination,若是一般的組合,n取k只要一行搞定
(1..n).to_a.combination(k).to_a
若C3取2就變成
[1, 2], [1, 3], [2, 3]

但是因為同事要的表示法不同。我就再想了一下,仍然是外行人的寫法。同事要的是組合,但他的表示法比較像排列,所以我只好折衷一下。
利用Ruby內建的permutation:
#!/usr/bin/env ruby
require 'set'
if __FILE__ == $0
  all=5
  want=2
  strArr=Array.new(want, 1) + Array.new((all-want), 0)
  strSet = Set.new(strArr.permutation.to_a)
  for str in strSet
    puts str.to_s
  end
end


這個若是C3取1,在Mac內建的1.8.7版是
100
010
001
但是用1.9.3卻是
[1, 0, 0]
[0, 1, 0]
[0, 0, 1]
我這個外行人還真的不懂。

Ruby對我來說真是個複雜的語言,下次再試試Lisp或Fortran吧
再Update:高見龍大神的做法
def get_combinations(n, m)
  combinations = []
  (0..n-1).to_a.combination(m) do |c|
    array = Array.new(n, 0)
    c.each { |i| array[i] = 1 }
    combinations << array.join
  end
  combinations
end
原來的寫法:
#!/usr/bin/env ruby

class Combinations

  # @param theValue [Array]
  def addList(theValue)
    @instList.concat([theValue])
  end


  def combinations(all, want)
    if (all < want)
      puts 'error, all must > want'
      return -1;
    end
    @instList = Array.new()
    calc('', all, want)
    return @instList
  end


  def calc(before, all, want)
    if want == 0
      addList(before+'0'*all)
    else
      if all == want
        addList(before+'1'*all)
      else
        if all == 1 then
          addList(before+want)
        else 
          calc(before+'0', all-1, want)
          calc(before+'1', all-1, want-1)
        end
      end
    end
  end
end

if __FILE__ == $0
  ci = Combinations.new
  list = ci.combinations(5, 3)
  puts "Total: ${list.length}"

  for str in list
    puts str
  end
end

留言

這個網誌中的熱門文章

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

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

在Windows Server設定L2TP over IPSec VPN

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