スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

二項演算の順序を指定する括弧の付け方を列挙するRubyプログラム

英語でいうところのbinary bracketingsを求めるRubyプログラムの紹介。例えば、x+y-zに対して、(x+y)-z、x+(y-z)を返す、といった具合です。

MathWorld:Bracketing
MathWorld:Binary Bracketing

実行結果

( 1 + ( 2 + 3 ) ) = 6
( ( 1 + 2 ) + 3 ) = 6
括弧の付け方の数 = 2

( 1 + ( 2 + ( 3 + 4 ) ) ) = 10
( 1 + ( ( 2 + 3 ) + 4 ) ) = 10
( ( 1 + 2 ) + ( 3 + 4 ) ) = 10
( ( 1 + ( 2 + 3 ) ) + 4 ) = 10
( ( ( 1 + 2 ) + 3 ) + 4 ) = 10
括弧の付け方の数 = 5

( 1 + ( 2 + ( 3 + ( 4 + 5 ) ) ) ) = 15
( 1 + ( 2 + ( ( 3 + 4 ) + 5 ) ) ) = 15
( 1 + ( ( 2 + 3 ) + ( 4 + 5 ) ) ) = 15
( 1 + ( ( 2 + ( 3 + 4 ) ) + 5 ) ) = 15
( 1 + ( ( ( 2 + 3 ) + 4 ) + 5 ) ) = 15
( ( 1 + 2 ) + ( 3 + ( 4 + 5 ) ) ) = 15
( ( 1 + 2 ) + ( ( 3 + 4 ) + 5 ) ) = 15
( ( 1 + ( 2 + 3 ) ) + ( 4 + 5 ) ) = 15
( ( ( 1 + 2 ) + 3 ) + ( 4 + 5 ) ) = 15
( ( 1 + ( 2 + ( 3 + 4 ) ) ) + 5 ) = 15
( ( 1 + ( ( 2 + 3 ) + 4 ) ) + 5 ) = 15
( ( ( 1 + 2 ) + ( 3 + 4 ) ) + 5 ) = 15
( ( ( 1 + ( 2 + 3 ) ) + 4 ) + 5 ) = 15
( ( ( ( 1 + 2 ) + 3 ) + 4 ) + 5 ) = 15
括弧の付け方の数 = 14

加法や乗法などの演算において括弧をどのようにつけても演算結果が変わらないことを、結合法則が成り立つといいます。

ソースプログラム

#!ruby -Ks

def binary_bracketings(a)
  return if a == nil && a.size % 2 == 0  # 文法エラー
  case a.size
  when 1
    [[a[0]]]
  when 3
    [['(', a[0], a[1], a[2], ')']]
  else  # 5以上の奇数
    result = []
    0.step(a.size-3, 2){ |i|
      binary_bracketings(a[0..i]).each{ |ary1| 
        binary_bracketings(a[i+2..-1]).each{ |ary2| 
          result << ['('] + ary1 + [a[i+1]] + ary2 + [')']
        }
      }
    }
    result
  end
end

# ======================================

if __FILE__ == $0

fms = [
  [1, '+', 2, '+', 3],                  # 3つの数
  [1, '+', 2, '+', 3, '+', 4],          # 4つの数
  [1, '+', 2, '+', 3, '+', 4, '+', 5],  # 5つの数
]

fms.each{ |fm|
  bkt_fms = binary_bracketings(fm)
  bkt_fms.each{ |elem|
    fm_str = elem.join(' ')
    puts "#{fm_str} = #{eval(fm_str)}"
  }
  puts "括弧の付け方の数 = #{bkt_fms.size}"; puts
}

end

カタラン数との関係

n+1個の数に対する括弧の付け方の数は、n番目のカタラン数C_nに一致することが知られています。カタラン数については、以下をお読みください:

Wikipedia:カタラン数
MathWorld:Catalan Number

結城浩『数学ガール』にも、カタラン数が登場します。

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。