星期五, 4月 13, 2012

求出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

沒有留言: