201104

Ruby


ゴロム定規

最短ゴロム定規を出力してみた。

def is_Golomb_ruler(ary)
  n = ary.size
  a = []
  (0..n - 2).each{|i|
    (i + 1..n - 1).each{|j|
      k = ary[j] - ary[i]
      if a.include?(k)
        return false
      else
        a << k
      end
    }
  }
  true
end

# 対称型を含む
def A(deg, l)
  a = []
  (1..l).to_a.combination(deg - 1){|c|
    ary = [0] + c
    a << ary if is_Golomb_ruler(ary)
  }
  a
end

# 対称型を省く
def B(deg, l)
  a = []
  A(deg, l).each{|ary|
    if !a.include?(ary.map{|i| ary[-1] - i}.reverse)
      a << ary
      p ary
    end
  }
end

B(2,  1)
B(3,  3)
B(4,  6)
B(5, 11)
B(6, 17)
B(7, 25)

出力結果

[0, 1]

[0, 1, 3]

[0, 1, 4, 6]

[0, 1, 4, 9, 11]

[0, 2, 7, 8, 11]

[0, 1, 4, 10, 12, 17]

[0, 1, 4, 10, 15, 17]

[0, 1, 8, 11, 13, 17]

[0, 1, 8, 12, 14, 17]

[0, 1, 4, 10, 18, 23, 25]

[0, 1, 7, 11, 20, 23, 25]

[0, 1, 11, 16, 19, 23, 25]

[0, 2, 3, 10, 16, 21, 25]

[0, 2, 7, 13, 21, 22, 25]