DouKaku?beta

challenge 自然数の分割 

自然数nとm(n>=m>0)が与えられたとき，nをm個の非負の整数の和で表すやり方を全て出力してください．
その際，和の組(x_1, ..., x_m)は大きい順に出力してください．
ここでm = 3の時の「(a, b, c)が(A, B, C)より大きい」とは
(a > A)
(a == A) かつ (b > B)
(a == A) かつ (b == B) かつ (c > C)
のいずれかが成り立つとき(つまりは辞書的順序)とします．

例:n = 5, m = 3が与えられたときは
5, 0, 0,
4, 1, 0,
4, 0, 1,
3, 2, 0,
3, 1, 1,
...
0, 1, 4,
0, 0, 5,
を出力する．
post comment

Posted feedbacks - Nested

Flatten Hidden
追加して並び替えました。こんな感じでしょうか。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using System;
using System.Collections.Generic;
static class Program {
    static void Main(String[] args) {
        int n = int.Parse(args[0]), m = int.Parse(args[1]);
        List<int[]> result = new List<int[]>();
        Append(result, n, m, 0, new int[0]);
        result.Sort(delegate(int[] x, int[] y) {
            for(int i = 0; i < x.Length; i++) {
                if (x[i] != y[i]) {
                    return x[i].CompareTo(y[i]) * -1;
                }
            }
            return 0;
        });
        foreach(int[] res in result) {
            Console.WriteLine(string.Join(", ", Array.ConvertAll<int, string>(res,
                delegate(int x) { return x.ToString(); })));
        }
    }
    static void Append(List<int[]> result, int n, int m, int sum, int[] items) {
        if (m <= items.Length) {
            if (n == sum) {
                result.Add(items);
            }
        }
        else {
            List<int> temp = new List<int>(items);
            temp.Add(0);
            for(int i = 0; i + sum <= n; i++) {
                temp[temp.Count - 1] = i;
                Append(result, n, m, sum + i, temp.ToArray());
            }
        }
    }
}
なんということだ。Sort どころか List<int[]> すら要らなかった／(^o^)＼ 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
using System;
using System.Collections.Generic;
static class Program {
    static void Main(String[] args) {
        hoge(int.Parse(args[0]), 0, 0, new int[int.Parse(args[1])]);
    }
    static void hoge(int n, int m, int sum, int[] items) {
        if (items.Length <= m) {
            if (n == sum) {
                Console.WriteLine(string.Join(", ", Array.ConvertAll<int, string>(items, 
                    delegate(int x) { return x.ToString(); })));
            }
        }
        else {
            for(int i = n - sum; 0 <= i ; i--) {
                items[m] = i;
                hoge(n, m + 1, sum + i, items);
            }
        }
    }
}

とりえあず。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def sumPatterns(n:int, m:int) = {
  def sum(ns:List[int]) = (0 /: ns){_+_}
  def cmp(a:List[int],b:List[int]):boolean = {
    if(a.head == b.head) cmp(a.tail, b.tail)
    else if(a.head > b.head) true
    else false
  }

  ((List(List[int]())) /: List.make(m, 0 to n)){
    for(i <-_; j <-_) yield j::i
  }.filter(sum(_) == n).sort(cmp _)
}

普通に再帰で。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
<?php
function parts($a,$n,$m)
{
    if(--$m<=0)
    {    $a[]=$n;
        echo implode(',',$a),"\n";
        return;
    }
    $c=count($a);
    for($i=$n;$i>=0;--$i)
    {    $a[$c]=$i;
        parts($a,$n-$i,$m);
    }
}

parts(array(),$argv[1],$argv[2]);
?>

comprehension大活躍。

1
2
partitionNum n 1 = [[n]]
partitionNum n m = [(n-x):xs | x <- [0..n], xs <- partitionNum x (m-1)]

あちゃ。先こされた ^^

comprehensionって便利ですね。 List Comprehension - defmacro によるリストの内包表記 http://lambda.s55.xrea.com/Emacs.html のlist-of を利用してemacs-lispで書いてみました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
(defun partitionNum (a b)
  (if (= b 1)
      (list (list a))
    (let ((x 0) (l '()))
      (while (<= x a)
    (progn
      (setq l
        (append 
         l
         (list-of (append (list (- a x)) y)
              (y in (partitionNum x (- b 1))))))
      (setq x (+ x 1))))
      l)))
(print (partitionNum 5 3))

Schemeならsrfi-42でcomprehensionが使えます。

1
2
3
4
5
6
7
(use srfi-42)

(define (partition-num n m)
  (if (= m 1)
    `((,n))
    (list-ec (: x 0 (+ n 1)) (: xs (partition-num x (- m 1)))
             (cons (- n x) xs))))

n=5 m=3 の場合、

(reverse (list-ec (: a 6) (: b 6) (: c 6) (if (= 5 (+ a b c))) (list a b c)))

というコードが生成されれば良い。

→マクロで書いてみる。

→nとmがコンパイル時に決まらないから無理？

→生成したコードをevalする方針に変更。

とこんな風になりました。

;; comprehensionと再起の組み合わせであんなに短く書けるとは。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
(use srfi-1)
(use srfi-42)

(define (quolifiers upper-bound n-quos)
  (let1 gensyms (map (lambda (x) (gensym)) (iota n-quos))
    (values gensyms
            (map (lambda (sym) `(: ,sym ,upper-bound))
                 gensyms))))

(define (partition-num n m)
  (receive (syms form) (quolifiers (+ n 1) m)
    (eval `(reverse (list-ec ,@form (if (= ,n (+ ,@syms))) (list ,@syms)))
          scheme-report-environment)))

evalの第二引数は (interaction-environment) にするか (current-module) にするのが良いでしょう。

現在はscheme-report-environmentの値である「手続きそのもの」が渡っているので本来はエラーなのですが、Gaucheはチェックをさぼってデフォルトである(current-module)の値を使っているためにたまたま動作してしまっています。

(scheme-report-environment 5) とすればevalの引数として正しいものが渡りますが、その環境の中ではR5RSで定義されている手続きや構文しか見えないのでlist-ecはエラーになります。

高階関数を使った版。

コード長くなった、読みづらくなった。orz
1
2
3
4
5
import List

partitionNum n m = iterate f ([[]]: repeat []) !! m !! n  where
  f xs = tail $ snd $ mapAccumL g (repeat []) [0..] where
    g (y:ys) i = (zipWith (++) (map (map (i:)) xs) ys, y)
push とか unshift は元の配列を返してくれれば便利なのに。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function doukaku89(n, m){
  if(--m < 1) return [[n]];
  for(var r = [], i = n, x = 0; i >= 0; i--)
    for(var a = arguments.callee(n - i, m), j = 0, l = a.length; j < l; j++)
      r[x++] = (a[j].unshift(i), a[j]);
  return r;
}

(typeof alert != 'undefined' ? alert :
 typeof print != 'undefined' ? print :
 function($){ typeof WSH == 'object' && WSH.echo($) })(doukaku89(5, 3).join('\n'))

普通に再帰で。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;
public class PartNumber {
    public static void main(String[] args) {
        System.out.println(part(5, 3));    // => [[5, 0, 0], [4, 1, 0], ..., [0, 1, 4], [0, 0, 5]]
    }
    private static List<List<Integer>> part(int n, int m) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> item;
        if (m == 1) {
            item = new ArrayList<Integer>();
            item.add(n);
            res.add(item);
            return res;
        }
        for (int i = n; i >= 0; i--) {
            List<List<Integer>> r = part(n - i, m - 1);
            for (List<Integer> l : r) {
                item = new ArrayList<Integer>();
                item.add(i);
                item.addAll(l);
                res.add(item);
            }
        }
        return res;
    }
}
動的計画法で。
(n, m) = (32, 8)で実行した場合。
----
234[ms]
[4, 4, 4, 4, 4, 4, 4, 4]
[3, 4, 4, 4, 4, 4, 4, 5]
[3, 3, 4, 4, 4, 4, 5, 5]
   :
[0, 0, 0, 0, 0, 0, 1, 31]
[0, 0, 0, 0, 0, 0, 0, 32]
3319 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.*;

public class PartNumber {
    private static final Map<Key, Answer> answerTable = new HashMap<Key, Answer>();
    public static void main(String[] args) {
        long begin = System.currentTimeMillis();
        Answer answer = execute(32, 8);
        System.out.printf("%d[ms]%n", System.currentTimeMillis() - begin);
        for (int[] a : answer.set) {
            System.out.println(Arrays.toString(a));
        }
        System.out.println(answer.set.size());
    }
    
    public static Answer execute(int n, int m) {
        Key key = new Key(n, m);
        if(answerTable.containsKey(key)) {
            return answerTable.get(key);
        }
        Answer answer = new Answer(key);
        if(m <= 2) {
            for (int i = 0; i <= n/2; i++) {
                answer.set.add(new int[]{i, n-i});
            }
        } else {
            for (int i = 0; i <= n/m; i++) {
                answer.set.addAll(execute(n-i, m-1).marge(key, i).set);
            }
        }
        answerTable.put(key, answer);
        return answer;
    }
     
    static class Key {
        final int n;
        final int m;

        Key(int n, int m) {
            this.n = n;
            this.m = m;
        }
        
        @Override
        public int hashCode() {
            return 17 * n ^ m;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (!(obj instanceof Key)) return false;
            Key target = (Key) obj;
            return (this.n == target.n && this.m == target.m);
        }
    }
    
    static class Answer {
        private final Key k;
        private TreeSet<int[]> set;

        Answer(Key k) {
            this.k = k;
            this.set = new TreeSet<int[]>(
                new Comparator<int[]>() {
                    public int compare(int[] o1, int[] o2) {
                        assert o1.length == o2.length;
                        if(o1 == o2) return 0;
                        for (int i = 0; i < o1.length; i++) {
                            if(o1[i] != o2[i]) return o2[i] - o1[i];
                        }
                        return 0;
                    }
                });
        }
        boolean add(int x, int[] a) {
            assert a.length + 1 == k.m;
            int[] a2 = new int[k.m];
            a2[0] = x;
            System.arraycopy(a, 0, a2, 1, a.length);
            Arrays.sort(a2);
            return set.add(a2);
        }
        Answer marge(Key k, int x) {
            Answer answer = new Answer(k);
            for (int[] a : this.set) {
                answer.add(x, a);
            }
            return answer;
        }
    }
}
まちがえた。大きい数を左に詰めるのか！
でも、int[]の逆順ソートはArrays.sortではできない。
Integer[]にするしかないか…

修正。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package doukaku;

import java.util.*;

public class PartNumber {
    private static final Map<Key, Answer> answerTable = new HashMap<Key, Answer>();
    public static void main(String[] args) {
        long begin = System.currentTimeMillis();
        Answer answer = execute(32, 8);
        System.out.printf("%d[ms]%n", System.currentTimeMillis() - begin);
        for (Integer[] a : answer.set) {
            System.out.println(Arrays.toString(a));
        }
        System.out.println(answer.set.size());
    }
    
    public static Answer execute(int n, int m) {
        Key key = new Key(n, m);
        if(answerTable.containsKey(key)) {
            return answerTable.get(key);
        }
        Answer answer = new Answer(key);
        if(m <= 2) {
            for (int i = 0; i <= n/2; i++) {
                answer.set.add(new Integer[]{i, n-i});
            }
        } else {
            for (int i = 0; i <= n/m; i++) {
                answer.set.addAll(execute(n-i, m-1).marge(key, i).set);
            }
        }
        answerTable.put(key, answer);
        return answer;
    }
     
    static class Key {
        final int n;
        final int m;

        Key(int n, int m) {
            this.n = n;
            this.m = m;
        }
        
        @Override
        public int hashCode() {
            return 17 * n ^ m;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (!(obj instanceof Key)) return false;
            Key target = (Key) obj;
            return (this.n == target.n && this.m == target.m);
        }
    }
    
    static class Answer {
        private final Key k;
        private TreeSet<Integer[]> set;

        Answer(Key k) {
            this.k = k;
            this.set = new TreeSet<Integer[]>(
                new Comparator<Integer[]>() {
                    public int compare(Integer[] o1, Integer[] o2) {
                        assert o1.length == o2.length;
                        if(o1 == o2) return 0;
                        for (int i = 0; i < o1.length; i++) {
                            if(o1[i] != o2[i]) return o2[i] - o1[i];
                        }
                        return 0;
                    }
                });
        }
        boolean add(int x, Integer[] a) {
            assert a.length + 1 == k.m;
            Integer[] a2 = new Integer[k.m];
            a2[0] = x;
            System.arraycopy(a, 0, a2, 1, a.length);
            Arrays.sort(a2, Collections.reverseOrder());
            
            return set.add(a2);
        }
        Answer marge(Key k, int x) {
            Answer answer = new Answer(k);
            for (Integer[] a : this.set) {
                answer.add(x, a);
            }
            return answer;
        }
    }
}

う。根本的に間違えてた。 「組み合わせ」じゃなくて、「順列」なのね。 はじめからソートは要らなかったorz

何度もすみません。最初のコードとのdiffで

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
@@ -23,3 +23,3 @@
         if(m <= 2) {
-            for (int i = 0; i <= n/2; i++) {
+            for (int i = 0; i <= n; i++) {
                 answer.set.add(new int[]{i, n-i});
@@ -27,3 +27,3 @@
         } else {
-            for (int i = 0; i <= n/m; i++) {
+            for (int i = 0; i <= n; i++) {
                 answer.set.addAll(execute(n-i, m-1).marge(key, i).set);
@@ -80,3 +80,3 @@
             System.arraycopy(a, 0, a2, 1, a.length);
-            Arrays.sort(a2);
+
             return set.add(a2);

Javaが無いからと思ったのに、 完成したときには投稿されていたよ。 残念。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Bunkatsu {
    public static void main(String[] args) {
        printSum( 6, 3 );
    }

    public    static void printSum( int n, int m) {
        if( m <= 0 || n < m )
            return;
        
        int[]    prints = new int[m];
        subPrintSum( prints, 0, n, m );
    }
    
    public static void subPrintSum( int[] prints, int p, int zan, int m ) {
        if( p == m -1 ) {
            prints[p] = zan;

            for( int print : prints ) {
                System.out.print( print );
                System.out.print( "," );
            }
            System.out.println();
        }
        else
        {
            for( int i = zan ; i >= 0 ; --i ) {
                prints[p] = i;
                subPrintSum( prints, p+1, zan - i, m );
            }
        }
    }
}

まずは，非常に安直な実装で．

はじめに，0以上n以下の数値からなる要素m個のArrayについて，考えうる全ての組み合わせを求めます．例えば，n = 3, m =2 の場合は:

> [[0, 0], [0, 1], [0, 2], [0, 3],
>  [1, 0], [1, 1], [1, 2], [1, 3],
>  [2, 0], [2, 1], [2, 2], [2, 3],
>  [3, 0], [3, 1], [3, 2], [3, 3]]

次に，このArrayを走査し，総和がnと一致するものだけを抽出し，ソートして解とします:

> [[3, 0], [2, 1], [1, 2], [0, 3]]

添削，ツッコミ，diff希望します:-)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
require 'pp'

class NumericArray < Array
  def initialize(maxvalue, level)
    self[0, 0] = [0] * level
    @maxvalue = maxvalue
  end

  def succ
    self.dup.succ!
  end

  def succ!
    result = []
    carry = reverse.inject(1) do |carry, cur|
      if cur + carry < @maxvalue then
        result << cur + carry
        carry = 0
      else
        result << 0
        carry = 1
      end
    end
    return nil if carry == 1
    replace(result.reverse)
  end

  def sum
    inject(0) {|sum, i| i + sum}
  end
end


begin
  raise '2 arguments required.' if ARGV.size != 2
  sum, maxlevel = ARGV.map {|n| n.to_i }

  if sum <= 0 or maxlevel <= 0 then
    raise 'Arguments out of range.'
  end
rescue
  puts <<-_EOD_
#{File.basename($0)}: ERROR: #{$!}
usage: #{File.basename($0)} n m
  _EOD_
  exit(1)
end

xs = NumericArray.new(sum + 1, maxlevel)
result = []
begin
  result << xs.dup
end while xs.succ!.nil? == false

pp result.select {|list| list.sum == sum}.sort.reverse

再帰 & yieldで

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
using System;
using System.Collections.Generic;

class Program {
    static IEnumerable<string> PartNum(int n, int m) {
        if (m == 1) {
            yield return n.ToString();
        } else if (m > 1) {
            for (int i = 0; i <= n; i++)
                foreach (string s in PartNum(i, m - 1))
                    yield return (n - i).ToString() + ", " + s;
        }
    }
    static void Main(string[] args) {
        foreach (string s in PartNum(5, 3))
            Console.WriteLine(s);
    }
}

rubyが無かったので書いてみたら、もうあった orz

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def part_number(n, m)
  return [[n]] if m == 1
  table = Array.new(n+1)
  0.upto(n) do |i|
    list = []
    0.upto(i) do |j|
      list << [i-j, j]
    end
    table[i] = list
  end
  3.upto(m) do |p|
    new_table = Array.new(n+1)