18815


「nをk個の相異なる数に分割する」場合の数をf(n, k)とします。

例えば、10 = 1 + 2 + 7 = 1 + 3 + 6 = 1 + 4 + 5 = 2 + 3 + 5  
なので、f(10, 3) = 4です。

f(n, k)を高速に求めるにはどのようにすればよろしいでしょうか？

以下大変遅いコードです。

[code]

    # nをk個の相異なる数（最大値がl）に分割
    def g(n, l, k)
      return 1 if n == l && k == 1
      # 末尾がiのものにlを追加
      (1..l - 1).inject(0){|s, i| s += g(n - l, i, k - 1)}
    end
    
    # nをk個の相異なる数に分割
    def f(n, k)
      (1..n).inject(0){|s, l| s += g(n, l, k)}
    end
    
    # 以下検証のためp(n | 和因子は相異なる)を求めてみる
    def A000009(n)
      return 1 if n == 0
      (1..n).inject(0){|s, k| s += f(n, k)}
    end
    p (0..20).map{|i| A000009(i)}
    
[/code]

実行結果  
[1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64]  
（p(n |
和因子は相異なる)については、[オイラーの分割恒等式をプログラミングで確認するには？](https://ja.stackoverflow.com/questions/9548/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%E5%88%86%E5%89%B2%E6%81%92%E7%AD%89%E5%BC%8F%E3%82%92%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%A7%E7%A2%BA%E8%AA%8D%E3%81%99%E3%82%8B%E3%81%AB%E3%81%AF)
で質問しました。）


CC BY-SA 3.0
2015-11-12T13:52:46.530
18746
2016-02-20T08:30:32.863
2017-04-13T12:52:39.113
-1
5363
question
ruby アルゴリズム haskell
「nをk個の相異なる数に分割する」場合の数を高速に求めるには？


数学の専門家ではないので、これがベストな解かは分かりませんが、ミリ秒レベルまでスピードアップできました。

`(1..n)`からk個選ぶ組み合わせを取得して、合計値がnになるものだけを数えています。  
<http://ref.xaio.jp/ruby/classes/array/combination>  
さらに探索の無駄を省くため、取りうる要素の最大値を最初に求めています。  
例えば`f(10, 3)`を求める場合は、最大値7（1 + 2 + **7** ）をまず求めて、`1..7`から３個選ぶ・・というような感じです。

[code]

    # nをk個の相異なる数（最大値がl）に分割
    def g(n, l, k)
      return 1 if n == l && k == 1
      # 末尾がiのものにlを追加
      (1..l - 1).inject(0){|s, i| s += g(n - l, i, k - 1)}
    end
    
    # nをk個の相異なる数に分割
    def f(n, k)
      (1..n).inject(0){|s, l| s += g(n, l, k)}
    end
    
    # 以下検証のためp(n | 和因子は相異なる)を求めてみる
    def A000009(n)
      return 1 if n == 0
      (1..n).inject(0){|s, k| s += f(n, k)}
    end
    
    ########## 以下を追加
    
    def using_combination(n, k)
      max = n - ((1...k).inject(:+) || 0)
      (1..max).to_a.combination(k).count {|values| values.inject(:+) == n }
    end
    
    def B000009(n)
      return 1 if n == 0
      (1..n).inject(0){|s, k| s += using_combination(n, k)}
    end
    
    require 'benchmark'
    
    Benchmark.bm 20 do |r|
      result1, result2 = nil
    
      r.report 'Original' do
        result1 =  (0..20).map{|i| A000009(i)}
      end
      r.report 'UsingCombination' do
        result2 =  (0..20).map{|i| B000009(i)}
      end
    
      raise 'The results are NOT equal' if result1 != result2
      puts 'ok.'
    end
    
[/code]

実行結果

[code]

                               user     system      total        real
    Original              21.390000   0.070000  21.460000 ( 21.508744)
    UsingCombination       0.000000   0.000000   0.000000 (  0.005335)
    ok.
    
[/code]


CC BY-SA 3.0
2015-11-13T05:12:39.657
18779
2015-11-13T05:19:07.100
2015-11-13T05:19:07.100
9608
9608
18746
answer


最大値ではなく、最小値に注目するとすぐに求まるようになりました。  
（combinationを使うとnを大きくしたとき大変遅くなりますが、  
以下のコードはそこまで遅くならない。例えば、n = 50としてみてください。）

[code]

    # nをk個の相異なる数（最小値がl）に分割
    def g0(n, l, k)
      return 1 if n == l && k == 1
      # 先頭がiのものにlを前から追加
      (l + 1..n - l).inject(0){|s, i| s += g0(n - l, i, k - 1)}
    end
    
    # nをk個の相異なる数に分割
    def f(n, k)
      (1..n).inject(0){|s, l| s += g0(n, l, k)}
    end
    
    # 以下検証のためp(n | 和因子は相異なる)を求めてみる
    def A000009(n)
      return 1 if n == 0
      (1..n).inject(0){|s, k| s += f(n, k)}
    end
    p (0..20).map{|i| A000009(i)}
    
[/code]

(追記)  
蛇足かもしれませんが、  
letrec さんの説明の補足と  
letrec さんのコードを少しだけいじったものを  
記しておきます。

[説明の補足]  
nをl以上の相異なるk個の数で分割する場合の数をg1(n, l, k)とする。

これは、最小値がlのもの, l + 1のもの, l + 2のもの, … に分類できるので、  
g1(n, l, k)  
= g1(n - l, l + 1, k - 1) + g1(n - l - 1, l + 2, k - 1) + g1(n - l - 2, l + 3,
k - 1) + …  
となる。

また、  
g1(n - l, l + 1, k - 1) ≧ g1(n - l - 1, l + 2, k - 1) ≧ g1(n - l - 2, l + 3, k
- 1) ≧ …  
となっている。  
この理由は以下の通りです  
a > 0 とする。  
n - l - aのk'個の相異なる数への分割(最小値はl + a + 1以上)  
(m1, … , mk')に対し、  
(m1, … , mk' + 1)を作ると、  
これはn - l - a + 1のk'個の相異なる数への分割(最小値l + a + 1以上)である。  
当然、n - l - a + 1のk'個の相異なる数への分割(最小値l + a以上)になっている。  
よって、  
g1(n - l - a + 1, l + a, k - 1) ≧ g1(n - l - a, l + a + 1, k - 1)

よって、  
g1(n - l, l + 1, k - 1), g1(n - l - 1, l + 2, k - 1), g1(n - l - 2, l + 3, k -
1), …  
と計算していき、その結果が0となった時点で計算を打ち切ればよい。

さて、求めるべきf(n, k)はg1(n, 1, k)に他ならない。

[コード]

[code]

    # nをl以上の相異なるk個の数で分割
    def g1(n, l, k)
      return 0 if n < l
      return 1 if k == 1
      s = 0
      (l + 1..n).each{|i|
        v = g1(n - i + 1, i, k - 1)
        break if v == 0
        s += v
      }
      return s
    end
    
    # nをk個の相異なる数に分割
    def f(n, k)
      g1(n, 1, k)
    end
    
    def A000009(n)
      return 1 if n == 0
      (1..n).inject(0){|s, k| s += f(n, k)}
    end
    p (0..20).map{|i| A000009(i)}
    
[/code]

(さらに追記)  
再帰よりDP の方が速い。

[code]

    def f1(n, k)
      a = []
      (k + 1).times{a << Array.new(n + 1){0}}
      a[0][0] = 1
      # 足し合わせる最大がx
      (1..n).each{|x|
        b = Marshal.load(Marshal.dump(a))
        (1..k).each{|i| (0..n - x).each{|j| b[i][j + x] += a[i - 1][j]}}
        a = b
      }
      a[-1][-1]
    end
    
    p f1(200, 10)
    
    # nをl以上の相異なるk個の数で分割
    def g1(n, l, k)
      return 0 if n < l
      return 1 if k == 1
      s = 0
      (l + 1..n).each{|i|
        v = g1(n - i + 1, i, k - 1)
        break if v == 0
        s += v
      }
      return s
    end
    
    # nをk個の相異なる数に分割
    def f(n, k)
      g1(n, 1, k)
    end
    
    p f(200, 10)
    
[/code]

実行結果  
98762607  
98762607


CC BY-SA 3.0
2015-11-13T10:33:56.073
18791
2016-02-20T08:30:32.863
2016-02-20T08:30:32.863
5363
5363
18746
answer


以下のコード中の`g_`はnをmin以上の相異なるk個の数を使って分割する場合の数を数え上げる関数です.  
k個の相異なる数への分割(最小値l)を(l,...,m)と数の昇順に書くとすると,分割(l+1,...,m)に対して分割(l,...,m+1)が考えられるので,`g_`でのリストの走査において結果が0となるような要素が現れれば,それ以降のリストの走査を打ち切ることができます.

Ruby:  

[code]

    # nをmin以上の相異なるk個の数で分割
    def g_(n, min, k)
      return 0 if n < min
      return 1 if k == 1
      sum = 0
      for l in (min..n)
        v = g_(n-l, l+1, k-1)
        break if v == 0
        sum += v
      end
      return sum
    end
    
    # nをk個の相異なる数に分割
    def f(n, k)
      g_(n,1,k)
    end
    
    def A000009(n)
      return 1 if n == 0
      (1..n).inject(0){|s, k| s += f(n, k)}
    end
    p (0..20).map{|i| A000009(i)}
    
[/code]

Haskell:  

[code]

    main = print $ map a000009' [1..20]
    
    a000009' n = sum (map (\x -> f n x) [1..n])
    
    f n k = g' n k 1
    
    -- nを最小値min以上の相異なるk個の数で分割
    g' n _ min
       | n < min = 0
    g' n 1 min = 1
    g' n k min = sum (mapUntil (==0) (\l -> g' (n-l) (k-1) (l+1)) [min..])
    
    mapUntil pred f (x:rest) = let v = f x
                               in if pred v
                                  then []
                                  else v:mapUntil pred f rest
    mapUntil _ _ [] = []
    
[/code]


CC BY-SA 3.0
2015-11-14T12:28:53.627
18815
2015-11-18T09:07:31.373
2015-11-18T09:07:31.373
13199
13199
18746
answer