自然数の分割（別表現） DouKaku?

正整数の分割といったとき，同じ組み合わせのもの同じ分割とみなし，
0 を除いて降順に並べたものを指すことも多いのではないかと思います．

たとえば，

partitions 1  ⇒ [[1]]
partitions 2  ⇒ [[2],[1,1]]
partitions 3  ⇒ [[3],[2,1],[1,1,1]]
partitions 4  ⇒ [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]
partitions 5  ⇒ [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]
partitions 6  ⇒ [[6],[5,1],[4,2],[3,3],[4,1,1],[3,2,1],[2,2,2],[3,1,1,1]
                 ,[2,2,1,1],[2,1,1,1,1],[1,1,1,1,1,1]]

すなわち，

- 1つの分割は非増加列
- 分割は長さが短いものが先
- 同じ長さの分割では辞書順で大きいものが先

という規則でならべたものです．一つの分割に一つのヤング図形が対応します．
たとえば、5 の分割に対応するヤング図形を列挙すると以下 7 つのようになります．

□□□□□
               
□□□□
□

□□□
□□

□□□
□
□

□□
□□
□

□□
□
□
□

□
□
□
□
□

お題：
正整数を与えられたとき上の意味での分割に対応するヤング図形をすべて
標準出力に印字する関数 young を定義してください．ヤング図形の出力は
上の例のように文字'□'を並べてください．

young 50 の出力をファイルにリダイレクトしたときの処理時間はどの程度
かかったかもCPUスペックとあわせt教えてください．

see: ヤング図形

ナイーブに、分割してから長さでソート。時間とファイルサイズはこんな感じ (on Pen4 2GHz, Linux, GHC6.6.1, compiled)。なお50の場合の解の総数は204226個でした。合ってる?

[shiro@scherzo ~]$ time ./Main > /dev/null

real 0m17.715s
user 0m16.241s
sys 0m0.489s
[shiro@scherzo ~]$ time ./Main > x

real 0m20.210s
user 0m17.327s
sys 0m1.230s
[shiro@scherzo ~]$ ls -l x
-rw-rw-r-- 1 shiro shiro 33643344 Nov 29 16:43 x

module Main where
import Data.List
import qualified System.IO.UTF8 as U

partitionNum n = sortBy cmp $ pttn n n
  where cmp a b | length a < length b  = LT
                | length a == length b = EQ
                | otherwise            = GT
        pttn 0 _ = [[]]
        pttn n k = [(n-x):xs | x <- [max (n-k) 0..n-1], xs <- pttn x (n-x)]

main = U.putStr $ unlines $ foldr chunk [] $ partitionNum 50
  where chunk ns r = map (\n -> replicate n '□') ns ++ [""] ++ r

Pen4 2.8Ghz, WinXP, VS2008 Beta2

合計204226件

ファイルリダイレクト 23.109375秒でした。

出力にやたら時間がかかってます。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace 自然数
{
    class Program
    {
        static void Main(string[] args)
        {
            DateTime prev = DateTime.Now;
            young(50);
            Console.WriteLine((DateTime.Now - prev).TotalSeconds);
        }

        static void young(int n)
        {
            List<int[]> youngList = new List<int[]>();
            Stack<int> stack = new Stack<int>();

            for( int i = n ; i > 0 ; --i )
                subYoung( youngList, stack, i, n-i );

            var x = from y in youngList
                    orderby y.Count() ascending
                    select y;

            foreach (int[] list in x)
            {
                foreach (int i in list)
                    Console.WriteLine( new string( '□', i ) );

                Console.WriteLine();
            }

            Console.WriteLine(youngList.Count());
        }

        static void subYoung( List<int[]> youngList, Stack<int> stack, int num, int zan )
        {
            stack.Push(num);

            if (zan == 0)
            {
                youngList.Add(stack.Reverse().ToArray());
            }
            else
            {
                for (int i = zan >= num ? num : zan; i > 0; --i)
                {
                    subYoung(youngList, stack, i, zan - i);
                }
            }

            stack.Pop();
        }
    }
}

Javaでやってみました。 MacOSX 10.5、2.5GHz PowerPC G5です。

java -Xmx256m Yang 50 > result 52.79s user 58.27s system 97% cpu 1:53.38 total

出力ルーチンが遅いようで列挙するだけの場合の処理時間は、

java -Xmx256m Yang 50 4.34s user 0.49s system 98% cpu 4.882 total

総数は、204226個でした。メモリの使用効率はもう少し考えないといけません...

import java.util.*;

public class Yang{

  ArrayList[] table;

  public Yang(int a){
    table = new ArrayList[a+1];
  }

  public ArrayList partitions(int value){
    ArrayList list = new ArrayList();
    ArrayList l0;
    l0 = new ArrayList();
    l0.add(new Integer(value));
    list.add(l0);
    for(int i = 1; i < value; i++){
      int v = value  - i;
      ArrayList l;
      if(table[i] != null){
     l = table[i];
      }else{
     l = partitions(i);
    table[i] = l;
      }
      Iterator it = l.iterator();
      while(it.hasNext()){
    l0 = (ArrayList)(it.next());
    if(((Integer)(l0.get(0))).intValue() <= v){
      ArrayList l1 = new ArrayList();
      l1.addAll(l0);
      l1.add(0, new Integer(v));
      list.add(l1);
    }
      }
    }
    return list;
  }

  public static void output(ArrayList list){
    Iterator it = list.iterator();
    while(it.hasNext()){
      int v = ((Integer)(it.next())).intValue();
      for(int i = 0; i < v; i++){
    System.out.print("□");
      }
      System.out.println();
    }
  }

  public static void main(String[] args){
    int a = Integer.parseInt(args[0]);
    Yang yang = new Yang(a);
    ArrayList l = yang.partitions(a);
    //System.err.println(l.size());
    Iterator it = l.iterator();
    while(it.hasNext()){
      output((ArrayList)(it.next()));
      System.out.println();
    }
  }

}

ソートしたら負けな気がした。

# -*- coding: utf-8 -*-

import sys

def m_partitions(n, m, l):
    if m == 1:
        if n <= l:
            yield [n]
    else:
        for i in xrange(min(n - m + 1, l), 0, - 1):
            for p in m_partitions(n - i, m - 1, min(i, l)):
                yield [i] + p

def partitions(n):
    for i in xrange(1, 1 + n):
        for p in m_partitions(n, i, n - i + 1):
            yield p

def young(n):
    for pattern in partitions(n):
        for m in pattern:
            print 'â–¡' * m
        print

def main(args):
    if len(args) == 1:
        n = int(args[0])
    else:
        n = 5

    young(n)

if __name__ == '__main__':
    main(sys.argv[1:])

実行時間を書くのを忘れてた。 AMD Athlon 64 X2 4400+ で 17.839 sec です。

C++ STL。出力だけでなく、イテレータまわしてるとこも遅いかも。

Pen4 3.06GHz, WinXP SP2, VS2005 count:204226 time[s]:19.937

#include <time.h>
#include <iostream>
#include <vector>

int young_sub(int n, int d, std::vector<int>& stack)
{
    if (n <= 0)
    {
        for (std::vector<int>::iterator li = stack.begin(); li != stack.end(); li++)
        {
            int n = *li;
            while (n--) { std::cout << "□"; }
            std::cout << std::endl;
        }
        std::cout << std::endl;
        return 1;
    }

    int count = 0;
    for (int i = ((n < d) ? n: d); i > 0; i--)
    {
        stack.push_back(i);
        count += young_sub(n - i, i, stack);
        stack.pop_back();
    }
    return count;
}

int young(int n)
{
    if (n < 1)
        return 0;
    std::vector<int> stack;
    stack.reserve(n);
    return young_sub(n, n, stack);
}

int main(int argc, char* argv[])
{
    if (argc < 2)
        return -1;
    int v = atoi(argv[1]);

    clock_t s = clock();
    int count = young(v);
    clock_t e = clock();

    std::cout << "count:"   << count << std::endl;
    std::cout << "time[s]:" << ((double)(e-s)/CLOCKS_PER_SEC) << std::endl;
    return count;
}

再帰＆yieldで n=50で204226件、3375 msでした。

Core2 Duo 6300 @ 1.86GHz, WinXP Pro, VS2005

using System;
using System.Collections.Generic;

class Program {
    static IEnumerable<string> Young2(int n, int m) {
        if (n <= m) yield return new string('□', n) + '\n';

        for (int i = Math.Min(n - 1, m); i > 0; i--)
            foreach (string s in Young2(n - i, i))
                yield return new string('□', i) + '\n' + s;
    }
    static IEnumerable<string> Young(int n) {
        return (n <= 0) ? new string[] {} : Young2(n, n);
    }
    static void Main(string[] args) {
        foreach (string s in Young(50))
            Console.WriteLine(s);
    }   
}

出力文字列をStringBuilder.Appendして一気に書き出すようにかえたら3.671875秒になった。

"□"の代わりに"[]"にした。

Windows XP
システムのプロパティ
  Pentium(R) 4 CPU 2.40GHz
  2.41 GHz, 0.99 GB RAM
ghc -O3 (GHC6.8.1)
ファイルにリダイレクトで５秒くらい。

nulにリダイレクトしたら１分くらいかかった。
nulへの出力は時間がかかるのね。

main = putStr $ unlines $ map (unlines . map (bou!!))
  $ partitions 50 where
  bou = iterate ("[]"++) ""

partitions n = f n n where
  f 0 _ = [[]]
  f n m = [m',m'-1..1] >>= (\x -> map (x:) (f (n-x) x)) where m' = min m n

私（#4505,#4507）と同じ間違いですよね？(^_^;

降順リストは [m',m'-1..1] って書けばいいんですね。なるほど。

スピードをちょっと気にしてみた。

ソート無しだとむしろ再帰回数が増えてしまうような。で考えてみたらあり得る分割数は分かっているのだから、素直再帰+バケツソートで良いのではなかろうか。

途中でひとつGauche 0.8.12の欠点発見。出力がリダイレクトされてても標準出力がラインバッファリングになってるためにめちゃくちゃシステムコールに時間をとられる。今回はフルバッファリングに変えるコードを足してある。あとwith-port-lockingは普段は気にする必要がないと思うけど、今回のケースでは0.5秒くらい速くなった。

スペックはPen4 2GHz, Linux, Gauche-0.8.12.

[shiro@scherzo ~]$ time gosh ./tt.scm 50 > x

real 0m6.261s
user 0m5.664s
sys 0m0.399s

;; -*- coding: utf-8 -*-
(use srfi-43)

(define (partition-num n)
  (define bins (make-vector n '()))
  (define (rec n k r)
    (if (= n 0)
      (let1 k (- (length r) 1)
        (vector-set! bins k (cons (reverse r) (vector-ref bins k))))
      (let loop ((x (clamp (- n k) 0)))
        (unless (= x n)
          (rec x (- n x) (cons (- n x) r))
          (loop (+ x 1))))))
  (rec n n '())
  bins)

(define (show bins)
  (define bars
    (vector-map (lambda (i _) (string-append (make-string (+ i 1) #\□) "\n"))
                bins))
  (vector-for-each (lambda (i bss)
                     (dolist (bs (reverse bss))
                       (dolist (b bs)
                         (display (vector-ref bars (- b 1))))
                       (newline)))
                   bins))
                   
(define (main args)
  (set! (port-buffering (current-output-port)) :full)
  (with-port-locking (current-output-port)
    (cut show (partition-num (x->integer (cadr args)))))
  0)

単純に再帰。 Windows上のVM、Intel Core2 2.4GHz で 14秒でした。

def part(n, mx, a, i)
  if n == 0
    i.times {|j| puts '□'*a[j] }
    puts
  else
    [n, mx].min.downto(1) do |k|
      a[i] = k
      part(n-k, k, a, i+1)
    end
  end
end

def young(n)
  part(n, n, Array.new(n), 0)
end

□の代わりに'O'にしてます。

Pentium M 1.73MHz, Fedora 7という環境で/dev/nullへのリダイレクトで0.681秒、ファイルへのリダイレクトで0.726秒です。

[xsd@celldev dk96]$ time ./dk96 50 > /dev/null

real    0m0.681s
user    0m0.679s
sys     0m0.001s

[xsd@celldev dk96]$ time ./dk96 50 > out.txt

real    0m0.726s
user    0m0.691s
sys     0m0.036s

ちなみに、n=80のときで69秒でした。

[yamaken@celldev dk96]$ time ./dk96 80 > /dev/null

real    1m9.190s
user    1m9.100s
sys     0m0.077s

let young n =
  let makeO x acc = ((String.make x 'O') ^ "\n") :: acc in
  let rec out = function [] -> print_char '\n' | hd :: tl -> let _ = out tl in print_string hd in
  let rec loop r c acc =
    if c <> 0 then match r - c with
      | 0            -> let _ = out      (makeO c acc) in loop r (c-1) acc
      | x when x > 0 -> let _ = loop x c (makeO c acc) in loop r (c-1) acc
      | _            -> loop r r acc in
    loop n n []

let _ = young (int_of_string Sys.argv.(1))

> - 分割は長さが短いものが先
すみません、見落としてましたorz

＞Pentium M 1.73MHz

すいません。Pentium M 1.73GHzの間違いでした。

> - 分割は長さが短いものが先

ご指摘どうもです。（先ほどのは自分で減点しておきました）

もともと今回のアルゴリスムでやるつもりだったのが
map t $ reverse する前の n == 5 のときの結果を見たら
答えと合っていたので「あれ、map t $ reverse する必要ないのかな？」
と省いてました。

「n を『長さが m』より短くなるように」分割したヤング図形
を転置したものは
「n を一つ一つが『m 以下の数』になるように」分割したヤング図形
に対応しています。

改めて

Windows XP
システムのプロパティ
  Pentium(R) 4 CPU 2.40GHz
  2.41 GHz, 0.99 GB RAM
ghc -O3 (GHC6.8.1)
ファイルにリダイレクトで７秒くらい。

main = putStr $ unlines $ map (unlines . map (bou!!))
  $ partitions 50 where
  bou = iterate ("[]"++) ""

partitions n = map t $ reverse $ f n n where
  f 0 _ = [[]]
  f n m = [x:xs| x <- [m',m'-1..1], xs <- f (n-x) x] where m' = min m n
  t [] = []
  t xs = length xs: t (filter (>0) $ map (subtract 1) xs)

grep()の使い方に注目。Memoizeとの合わせ技で10秒ちょっと。ちなみにozdさんの#4498が同じ環境(MacBook Pro 2.33GHz; Mac OS X v10.4.11)で22秒。

Dan the Perl Monger

#!/usr/local/bin/perl
use strict;
use warnings;
use Memoize;

sub young {
    my $n = shift;
    die 'young($n); # where $n is an integer' unless $n;
    return [1] if $n == 1;
    my @result = ( [$n] );
    for my $k ( reverse 1 .. $n - 1 ) {
        push @result,
          map { [ $k, @$_ ] } grep { $k >= $_->[0] } young( $n - $k );
    }
    @result;
}

memoize 'young';

sub print_young{
    my $n = shift;
    local $\ = "\n";
    for my $a (young($n)){
        print '#' x $_ for @$a;
        print "=" x $n;
    }
}

my ($n, $quiet) = @ARGV;
$quiet ? young($n) : print_young($n);
__END__
% perl young.pl 5
#####
=====
####
#
=====
###
##
=====
###
#
#
=====
##
##
#
=====
##
#
#
#
=====
#
#
#
#
#
=====
% time perl young.pl 50 1
9.390u 0.783s 0:10.29 98.8%     0+0k 0+1io 0pf+0w
% time sh -c 'perl young.pl 50 | grep = | wc'
  204226  204226 10415526
10.903u 0.894s 0:11.82 99.7%    0+0k 0+3io 0pf+0w

再帰なしに挑戦。たぶんできたけど可読性がダメかも。

実行時間は Celeron 2.66 GHz で 0.8 秒弱ぐらいです。ほとんどの時間は出力にかかってます。□ の代わりに 'O' を使うと 0.45 秒ぐらいに。

#include <stdio.h>
#include <time.h>
#include <string.h>
#define N_MAX 256
#define BOXWIDTH (sizeof("□") - 1)

void print_young (int m, int a[]) {
  int i, j;
  char buf[4 * N_MAX], *p;
  for (p = buf, i = 0; i < m; i++) {
    for (j = 0; j < a[i]; j++, p += BOXWIDTH)
      memcpy(p, "□",  BOXWIDTH);
    *p++ = '\n';
  }
  *p = '\0';
  puts(buf);
}

void young (int n) {
  int buf[N_MAX], m;

  for (m = 1; m <= n; m++) {
    int *p = buf, *q = buf + m - 1, *r;

    *p = n - m + 1;
    for (r = p + 1; r <= q; r++) *r = 1;
    while (1) {
      int a, s, t;
      print_young (m, buf);
      if (*p - *q < 2) break;

      for (a = *q + 2, r = q, s = 0; *r < a; r--)
        s += *r - 1, *r = 1;
      s++, (*r)--, t = *r - 1, r++;
      for (; s >= t; r++) { *r += t; s -= t; }
      *r += s;
    }
  }
}

int main (int argc, char* argv[]) {
  clock_t start, end;
  start = clock();
  young ((argc >= 2) ? atoi(argv[1]) : 50);
  end = clock();

  fprintf(stderr, "%f sec.\n", (double)(end - start) / CLOCKS_PER_SEC);
  return 0;
}

なるほど！と思ったのですが、partitions 9で辞書式順序との不一致が生じるようです。
(...,[5,3,1],[4,4,1],[5,2,2],...)
実は私も考え直していて、同じく 9 で失敗したところでした。

> partitions 9で辞書式順序との不一致が生じるようです。
> (...,[5,3,1],[4,4,1],[5,2,2],...) 

ありゃ、そうですか。考え直します。
度々のご指摘感謝です。

(高さ) × (□の総数) × (その高さにある□の数の上下限) をテーブルにしてDP。

Core2 Duo 2.4GHz で2.366秒。

#include <stdio.h>
#include <stdlib.h>
#define MIN(a,b) ((a)<(b) ? (a) : (b))
#define N 256

int table[N][N][2];
int seq[N];
int cnt = 0;

void print_young(int d, int k, int m, int h, int n) {
  int i,j;
  if (d > 0) {
    for (i = MIN(m, table[d][k][1]); i >= table[d][k][0]; i--) {
      seq[h-d] = i;
      print_young(d-1, k-i, i, h, n);
    }
  } else {
    for (i = 0; i < h; i++) {
      for (j = 0; j < seq[i]; j++)
        printf("□");
      putchar('\n');
    }
    putchar('\n');
    ++cnt;
  }
}

void young(int n) {
  int i, j;
  for (i = 0; i < N; i++)
    table[1][i][0] = table[1][i][1] = i;
  for (i = 2; i < N; i++) {
    for (j = i; j < N; j++) {
      table[i][j][0] = (j-1) / i + 1; /* lower bound */
      table[i][j][1] = j - i + 1;     /* upper bound */
    }
  }
  for (i = 1; i <= n; i++) {
    print_young(i, n, n, i, n);
  }
}

int main(int argc, char **argv) {
  young((argc >= 2) ? atoi(argv[1]) : 50);
  printf("\n\n# %d\n", cnt);
  return 0;
}

テーブルとか要らなかったですねorz

ちなみに実行時間の99%はファイル書き込み時間でした。

#include <stdio.h>
#include <stdlib.h>
#define MIN(a,b) ((a)<(b) ? (a) : (b))
#define N 256
int seq[N];
int height;

void print_young(int d, int n, int ceil) {
  int i,j;
  int upper, lower;
  if (d > 0) {
    upper = n - d + 1;
    lower = (n-1) / d + 1;
    for (i = MIN(ceil, upper); i >= lower; i--) {
      seq[height-d] = i;
      print_young(d-1, n-i, i);
    }
  } else {
    for (i = 0; i < height; i++) {
      for (j = 0; j < seq[i]; j++)
        printf("□");
      putchar('\n');
    }
    putchar('\n');
  }
}

int main(int argc, char **argv) {
  int n = (argc >= 2) ? atoi(argv[1]) : 50;
  for (height = 1; height

DouKaku?

自然数の分割（別表現）

Posted feedbacks - Flatten