作者: Hiroshi Shinohara
日時: 2003/8/20(22:14)
Iconミニ講座３（正数の分割）
　今回は、正数の部分和への分解です。これは、５文字の文字列があるとして、
例えば、３文字と２文字の２つの単語として、辞書を参照するためのものです。
　５の分解でも、５（分解しない）、４＋１、３＋２、３＋１＋１、．．．と
いって、最後は１＋１＋１＋１＋１と、かなりのパターンが発生します。
　こういう面倒な繰り返しが必要な処理は、再帰処理を行うとプログラムが楽に
なることが多いみたいですね。

　処理は、５の例ですと、５から順次　５、４、３、２、１と引き算していく
やり方にしています。

　最初は、５から５を引くケースで、
　　余りは０です。　結果は［５］を返します。

　次は、５から４を引くケースで、
　　余りは１です。余りがある場合は、中間結果として［４］を保持して、
　　自分自身を更に呼んで（再帰）、余りの１を与えて、結果をもらいます。
　　その結果として［１］が返って来ます。中間結果の［４］に［１］を追加して
　　［４，１］を結果として返します。

　次は、５から３を引くケースで、
　　１回目の動作　中間結果１　［３］　余り　２　・・・余り処理のため再帰
　　２回目の動作　中間結果１　［２］　余り　０
　　　　　　　　　　　　　２　［１］　余り　１　・・・余り処理のため再帰
　　３回目の動作　　　結果１　［１］
　という動作を経ますので、結果は［３，２］と、［３，１，１］の２つが返り
　ます。

　こんな風な動作となります。

-----^ N_DIV.ICN ( date:03-08-20 time:19:43 ) --------------<cut here
####################
# 正数分割
####################
# n_div.icn Rev.1.0 2003/08/20 windy 風つかい H.S.
####################
# Usage n_div 正数
# 与えられた数字を部分和に分解する。
# 例:5->[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]
# This file is in the public domain.

procedure main(args)
  Usage := "n_div 正数"
  if *args   < 1 then stop(Usage) # コマンドライン引数が無ければ Usage表示
  if args[1] < 1 then stop(Usage) # 正数でなければ Usage表示

  # ↓正数分割 generatorから順次結果を取り出し
  every L := n_div(args[1]) do show_sl(L)
                          # ↑listの内容を表示する
end

####################
# 正数分割 generator
####################
# arg [1]: 分割される数（正数）（再帰の場合は、余り）
# value  : 分解結果の数 listに格納
# Usage  : every L := n_div(r) do ...
procedure n_div(r)
  if r < 1 then fail              # 念のため
  if r = 1 then return [1]        # 再帰終了

  # r >= 2 の場合
  every i :=  r to 1 by -1 do {   # r から順に　−１しながら
    rr := r -i                    # 元の数から引き算していく
    if rr = 0 then suspend [i]    # 余りが　０なら結果を返す。
              else suspend [i] ||| n_div(rr)
                             # ↑余りがでたら、再帰してその結果を listの末尾
                             # に追加。　||| は listの要素の追加演算子
  }                          # suspend は、複数の結果を返す return
end

# 以下は、Icon入門講座より

####################
# listの 内容表示
####################
# arg   : list
# value : null
# Usage : show_sl(L)
# 最終的に stringか numberが要素であること
# Icon入門講座（１３）,Icon入門講座３（１５）

procedure show_sl(list)
# listの内容表示（test／表示用）
  every writes(" ",!list)
  write()
  return
end
-----$ N_DIV.ICN ( lines:57 words:192 ) --------------------<cut here

　n_div 5 >ccc　としますと、こんな結果になります。
-----^ CCC ( date:03-08-20 time:19:44 ) --------------------<cut here
 5
 4 1
 3 2
 3 1 1
 2 3
 2 2 1
 2 1 2
 2 1 1 1
 1 4
 1 3 1
 1 2 2
 1 2 1 1
 1 1 3
 1 1 2 1
 1 1 1 2
 1 1 1 1 1
-----$ CCC ( lines:16 words:48 ) ---------------------------<cut here

　以上の結果を良く見ますと、５＝４＋１と１＋４や　３＋２と２＋３の両方が
現れています。　辞書検索は、どちらか一方を行えば、残りは入れ替えるだけで
人が判断できると思います。　ということで、片方だけにするために、結果は、
降順しか許さないという条件を付けましょう。　ということで、再帰の際に制限
を付けました。

-----^ N_DIVD.ICN ( date:03-08-20 time:19:42 ) -------------<cut here
####################
# 正数分割
####################
# n_divd.icn Rev.1.0 2003/08/20 windy 風つかい H.S.
####################
# Usage n_divd 正数
# 与えられた数字を部分和に分解する。結果は降順の分解のみ。
# 例:5->[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]
# This file is in the public domain.

procedure main(args)
  Usage := "n_divd 正数"
  if *args   < 1 then stop(Usage) # コマンドライン引数が無ければ Usage表示
  if args[1] < 1 then stop(Usage) # 正数でなければ Usage表示

  # ↓正数分割 generatorから順次結果を取り出し
  every L := n_divd(args[1]) do show_sl(L)
                          # ↑listの内容を表示する
end

####################
# 正数分割 generator
####################
# 5=3+2 等に分割する。分割は降順のみ許す。（例 5=2+3は除外）
# arg [1]: 分割される元の数（再帰の場合は、前の処理の余り）
#     [2]: 最大数  （5=2+2+1 の場合に、最初の 2の時 3が余るが、再帰して 3の
#          分割を始める時、3からではなく 2から始めるための細工。降順手当。）
# value  : 分解結果の数。listに格納
# Usage  : every L := n_divd(r) do ...
procedure n_divd(r,max)
  /max := r                       # 指定無きは、分割される元の数そのもの
  if r < 1 then fail              # 念のため
  if r = 1 then return [1]        # 再帰終了

  # r >= 2 の場合
  if r > max then rs := max       # 分割（取り去る）数の最大数の設定。
             else rs := r         # 分割される数か 最大数指定の 小さい方
  every i :=  rs to 1 by -1 do {  # 上記指定数〜１迄、順に−１しながら
    rr := r -i                    # 新たな余り
    if rr = 0      then suspend [i]                   # 余りが無ければ
    # 余りがあれば、再帰処理
    else if rr > i then suspend [i] ||| n_divd(rr,i)  # 余りが大き過ぎる時
                   else suspend [i] ||| n_divd(rr)
  }
end

# 以下は、Icon入門講座より

####################
# listの 内容表示
####################
# arg   : list
# value : null
# Usage : show_sl(L)
# 最終的に stringか numberが要素であること
# Icon入門講座（１３）,Icon入門講座３（１５）

procedure show_sl(list)
# listの内容表示（test／表示用）
  every writes(" ",!list)
  write()
  return
end
-----$ N_DIVD.ICN ( lines:63 words:231 ) -------------------<cut here

　n_divd 5 >ddd　とすると結果は、こうなります。　だいぶパターンが減り
ました。　それでも、未だ随分ありますので、分割数や最小数に制限をつけたい
と思います。それは、次回に。
-----^ DDD ( date:03-08-20 time:19:45 ) --------------------<cut here
 5
 4 1
 3 2
 3 1 1
 2 2 1
 2 1 1 1
 1 1 1 1 1
-----$ DDD ( lines:7 words:20 ) ----------------------------<cut here

風つかい(hshinoh@...)
IconのWWWは、  http://www.cs.arizona.edu/icon/
UniconのWWWは、http://unicon.sourceforge.net/index.html
BGM: Battery's not included ／ 森山威男＆杉本喜代志