image

  • フォト Amazonギフト券
    ※この時計の時刻は、閲覧しているパソコンのものであり、必ずしも正確な時間とは限りません

検索

最近のトラックバック

無料ブログはココログ

« doukaku.org の 自然数の分割 | トップページ | "恐れを知らぬ川上音二郎一座" 当日券での鑑賞はできず... »

2007-12-16

doukaku.org の 自然数の分割 (その2)

[4,1,0], [4,0,1] など組み合わせ的には同じものを区別せずに
一覧出力するようにしたものを作ってみた。

[5, 0, 0]
[4, 1, 0]
[3, 2, 0]
[3, 1, 1]
[2, 2, 1]
のように出力される。

$ cat PartNumber.java
// See http://ja.doukaku.org/89/lang/java/
//    javac PartNumber.java
//    java -cp . PartNumber 5 3

public class PartNumber {
    public static void main(String[] args) throws Exception {
        int n = Integer.parseInt(args[0]);
        int m = Integer.parseInt(args[1]);
        part("", n, n, m);
    }
    private static void part(String s, int last, int n, int m) {
        if (m == 1) {
            if (last >= n) {
                System.out.println("[" + s + n + "]");
            }
        } else for (int i = n; i >= 0; i--) {
            if (last >= i) {
                part(s + i + ", ", i, n - i, m - 1);
            }
        }
    }
}

$ cat PartNumber.rb 
# http://ja.doukaku.org/89/lang/ruby/
#   ruby PartNumber.rb
#   jruby PartNumber.rb

def solve(n, m, last, acc = [])
  if m == 1
    p acc << n  if last >= n
    return
  end
  n.downto(0) {|i|
    solve(n-i, m-1, i, acc[0..-1] << i)  if last >= i
  }
end

solve(5, 3, 5)

$ cat PartNumber.pl
% http://ja.doukaku.org/89/lang/prolog/
%   swipl -q -c PartNumber.pl

partNum(N, 1, [N], MIN) :- N =< MIN.
partNum(N, M, [J|L], MIN) :- M > 1, M1 is M - 1,
    between(0, N, I), J is N - I, J =< MIN, partNum(I, M1, L, J).

solve(N,M) :- forall(partNum(N, M, L, N), writeln(L)).

:- solve(5, 3).

走らせた結果を示そう。
$ java -cp . PartNumber 5 3
[5, 0, 0]
[4, 1, 0]
[3, 2, 0]
[3, 1, 1]
[2, 2, 1]

$ ruby PartNumber.rb      
[5, 0, 0]
[4, 1, 0]
[3, 2, 0]
[3, 1, 1]
[2, 2, 1]

$ swipl -q -c PartNumber.pl
[5, 0, 0]
[4, 1, 0]
[3, 2, 0]
[3, 1, 1]
[2, 2, 1]

« doukaku.org の 自然数の分割 | トップページ | "恐れを知らぬ川上音二郎一座" 当日券での鑑賞はできず... »

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/184434/17384172

この記事へのトラックバック一覧です: doukaku.org の 自然数の分割 (その2):

« doukaku.org の 自然数の分割 | トップページ | "恐れを知らぬ川上音二郎一座" 当日券での鑑賞はできず... »

mokuji

2013年12月
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        

google

  • twitter
  • __
  • _
    Googleボットチェッカー

合わせて読む

  • 合わせて読む
    フィードメーター - katoy: cocolog あわせて読みたい

リンク