辞書順で何番目か(Ruby)

辞書順(lexicographical order)に並べて何番目か、あるはn番目のものは何か。

要素に重複がないとして考える。数列 (1, 2, .... , n) の並べ替えとして解こう。


数列 (a1, .. , an) は辞書順で何番目か。

def number_in_lex_order(ary)
  n = ary.size
  return 1 if n <= 1
  idx = ary.sort.bsearch_index { _1 >= ary[0] }
  (1..n - 1).inject(:*) * idx + number_in_lex_order(ary[1..-1])
end

number_in_lex_order([2, 1, 5, 3, 4])    #=>29

ここでは、数列の左端の数字が、数列を昇順にソートした中で何番目に来るかがわからなければならない。それを i (=idx+1) とすると、そこまでで (n - 1)! * (i - 1) だけ既に(一桁少ない部分)数列が並んでいることになる(ただし n は ary の桁数)。
あとは左端の一桁を落として同じことを(再帰で)求め、すべての和をとってやれば求まる。


文字列などならば、ハッシュで数列に変換するテーブルを作ってやればよい。

str = "MATH"
h = "AHMT".each_char.with_index(1).to_h

number_in_lex_order(str.each_char.map { h[_1] })    #=>14

もっとも、文字列ならば Ruby の柔軟性(?)のおかげで、

number_in_lex_order("MATH".chars)    #=>14

で求まってしまうのだが。


これの逆、つまり辞書順でn番目の数列はどうなるか。この場合、数列の長さ(size)を与えることが必要である。

def nth_sequence_in_lex_order(n, size)
  i = 1
  table = (1..size - 1).map { i *= _1 }
  
  order = (1..size).to_a
  ans = []
  n -= 1
  size.pred.times do
    factorial = table.pop
    i = n / factorial
    n -= i * factorial
    ans << (a = order[i])
    order.delete(a)
    break if n <= 0
  end
  ans.concat(order)
end

やってみる。

nth_sequence_in_lex_order(29, 5)     #=>[2, 1, 5, 3, 4]

よさそうだ。

上と同様に、文字列でもやってみる。これも、ハッシュでテーブルを作り、Hash#invert する。

h = "AHMT".each_char.with_index(1).to_h.invert

nth_sequence_in_lex_order(14, 4).map { h[_1] }.join    #=>"MATH"

これもよさそうだ。


なお、いずれも不正入力には対応していない。

numo-gnuplot sample

qiita.com

ウィンドウで表示する場合。Linux Mint 20.3。

require "numo/gnuplot"

Numo.gnuplot do
  set terminal: "wxt font 'Noto Sans CJK JP,12'"
  set title: "グラフのタイトル"
  set xrange: 0..6
  set yrange: 0..60
  set xlabel: "x軸のラベル"
  set ylabel: "y軸のラベル"
  
  x = [1, 2, 3]
  y1 = [11, 25, 32]
  y2 = [21, 35, 42]
  y3 = [31, 45, 52]
  
  plot x, y1, {title: "系列1"},
       x, y2, {w: :lines, title: "系列2(線のみ)"},
       x, y3, {w: :linespoints, title: "系3(点と線)"},
       "x * 10", {title: "y = x * 10"}
end

sleep

20220529181731

単調非減少と単調非増加で配列(Enumerator)を切断する

要するにこれです。
atcoder.jp

配列 A が与えられます。 A を何箇所かで切って、A の連続した部分であるようないくつかの数列に分けます。 この時、分けられたあとの数列は全て、単調非減少または単調非増加な列になっている必要があります。

コード

Enumerable にこんなメソッドupdown_cutを生やしてみました。

module Enumerable
  def updown_cut
    e = to_enum
    updown = 0
    
    calc = ->(compare) {
      case updown
      when 0 then [compare, false]
      when -1
        case compare
        when -1, 0 then [-1, false]
        else [0, true]
        end
      else
        case compare
        when 1, 0 then [1, false]
        else [0, true]
        end
      end
    }
    
    begin
      a = e.next
    rescue StopIteration
      return self
    end
    
    pool = [a]
    loop do
      b = e.next
      updown, f = calc.(a <=> b)
      a = b
      if f
        yield pool
        pool = [a]
      else
        pool << a
      end
    end
    yield pool
    self
  end
end

 

使い方

配列(あるいは Enumerator)を単調非減少、あるいは単調非増加な配列になるよう切ってくれます。切られた配列はブロック変数に入ります。

[1, 2, 3, 2, 2, 1].updown_cut { p _1 }
#=>
#[1, 2, 3]
#[2, 2, 1]

ary = ([*1..7] * 2).shuffle
#=>[3, 1, 2, 7, 6, 7, 6, 5, 1, 5, 4, 4, 3, 2]
ary.enum_for(:updown_cut).to_a
#=>[[3, 1], [2, 7], [6, 7], [6, 5, 1], [5, 4, 4, 3, 2]]

str = ("abcdef" * 4).chars.shuffle.join
#=>"ecfdedcfecbabbbadfadcaef"
str.each_char.enum_for(:updown_cut).map(&:join)
#=>["ec", "fd", "edc", "fecba", "bbba", "df", "ad", "ca", "ef"]

 
いやあ、苦労しました。

Ractor でフィボナッチ数列

まずは小手調べ

takeするまで待って、takeするたびに無限に同じオブジェクトを返してくれる Ractor は、「Pull型通信」を使ってこんな風に作れる。

r = Ractor.new do
  loop { Ractor.yield 1 }
end

Array.new(5) { r.take }    #=>[1, 1, 1, 1, 1]

わかりやすいですね。

では、例えば単調増加列も簡単に作れる。

r = Ractor.new do
  i = 1
  loop do
    Ractor.yield i
    i += 1
  end
end

Array.new(5) { r.take }    #=>[1, 2, 3, 4, 5]

 

フィボナッチ数列を Ractor で計算してみる

こんなコードを書いてみた。

def fibonacci
  fib = Array.new(N + 1)
  
  2.times do |i|
    fib[i] = Ractor.new(i) do |j|
      loop { Ractor.yield j }
    end
  end
  
  (2..N).each do |i|
    fib[i] = Ractor.new(fib[i - 1], fib[i - 2]) do |a, b|
      e = a.take + b.take
      loop { Ractor.yield e }
    end
  end
  
  fib[N].take
end

fib[n]fib[n - 1]fib[n - 2]が計算するまで待ち(これらすべて Ractor オブジェクト)、双方が計算を終了したらtakeされるのを待つ。それで、takeされるたび、計算結果を返し続ける。

ってまあ、ほとんど意味のないプログラムだが、計算と一種の「メモ化」ですね。おもしろいといえばおもしろい。パフォーマンスはどうかというと、N = 3000 としてわたしの環境で 3.4秒くらい。3001個の Ractor オブジェクトが生成されるわけだが、どうなのかな。

なお、fib[3000].takeの結果は、

4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125

という具合です。

パスカルの三角形(Elixir)

obelisk.hatenablog.com
ここで Ruby でやっていることを、Elixir でやってみました。
こういうのを表示します。

              1               
             1 1              
            1 2 1             
           1 3 3 1            
          1 4 6 4 1           
        1 5 10 10 5 1         
       1 6 15 20 15 6 1       
     1 7 21 35 35 21 7 1      

 

コード

pascal_triangle.exs

defmodule PascalTriangle do
  def draw(1), do: [1]
  def draw(2), do: [1, 1]

  def draw(n) do
    [1] ++ (draw(n - 1) |> contract) ++ [1]
  end

  defp contract([]), do: []
  defp contract([_]), do: []

  defp contract([a1 | [a2 | rest]]) do
    [a1 + a2 | contract([a2 | rest])]
  end
end

defmodule ExString do
  def center(str, n) do
    s = String.length(str)
    a = div(n - s, 2)
    (String.duplicate(" ", a) <> str) |> String.pad_trailing(n)
  end
end

result =
  for i <- 1..8 do
    PascalTriangle.draw(i) |> Enum.join(" ") |> ExString.center(30)
  end

Enum.join(result, "\n") |> IO.puts()

Hit&Blow を Ruby で

qiita.comおもしろそうなので、自分でも書いてみた。
 

ルール

コンピュータの決めた、各桁に重複のない3桁の数を当てるゲーム。
当たらなかった場合、

  • 入力と桁の合っている数字の数を、ヒット
  • 入力と桁は合っていないが重複はしている数字の数を、ブロウ

として教えてくる。
 

実行例

各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 135
ヒット:1, ブロウ:0
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 315
ヒット:0, ブロウ:1
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 351
ヒット:0, ブロウ:1
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 124
ヒット:1, ブロウ:0
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 106
ヒット:1, ブロウ:1
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 160
ヒット:2, ブロウ:0
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 170
ヒット:2, ブロウ:0
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 180
ヒット:2, ブロウ:0
各桁のそれぞれちがう、3桁の数を入力して下さい(例:012): 190
正解です! 9回で当てました!

 

コード

hit_and_blow.rb

module Hit_and_Blow
  module_function
  
  N = 3
  
  def input
    expl = (0...N).to_a.join
    loop do
      print "各桁のそれぞれちがう、#{N}桁の数を入力して下さい(例:#{expl}): "
      s = gets.chomp.chars
      if s.size != N || s.uniq.size != N || s.any?(/\D/)
        puts "不正な入力です。"
      else
        return s
      end
    end
  end
  
  def judge(target, number)
    overlap = (target & number).size
    hit = target.zip(number).count { |a, b| a == b }
    [hit, overlap - hit]
  end
  
  def play
    target = [*"0".."9"].sample(N)
    (1..).each do |n|
      number = input
      
      if target == number
        puts "正解です! #{n}回で当てました!"
        break
      else
        hit, blow = judge(target, number)
        puts "ヒット:#{hit}, ブロウ:#{blow}"
      end
    end
  end
end

Hit_and_Blow.play

N = 3だと簡単ですが、N = 4にすると結構手ごわいです。