Comment detail

自然数の分割(別表現) (Nested Flatten)
正整数の分割といったとき,同じ組み合わせのもの同じ分割とみなし,
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教えてください.

Index

Feed

Other

Link

Pathtraq

loading...