自然数の分割 in Smalltalk DouKaku?

自然数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,
を出力する．

Squeak Smalltalk で。

| compo |
compo := [:nn :mm |
    mm = 1 ifTrue: [{{nn}}] ifFalse: [
        (nn to: 0 by: -1) inject: #() into: [:res :hd |
            res, ((compo copy fixTemps value: nn - hd value: mm - 1) collect: [:each | {hd}, each])]]].
World findATranscript: nil.
(compo copy fixTemps value: 5 value: 3) do: [:nums |
    Transcript cr.
    nums do: [:num | Transcript show: num printString, ',']]

Squeak Smalltalk で。

n から 0 までの整数をそれぞれの桁と見なす m 桁の表現（配列）をすべて生成（asDigitsToPower: m do: aBlock）させ、うち合計（sum）が n になるものだけ選びました。

効率は悪いのですが、比較的簡潔に書けるところが yuin さんの #4301、ihag さんの #4313、kkobayashi さんの #4342 を拝見していて気に入ったので。

| n m results |
n := 5.  m := 3.
results := OrderedCollection new.
(n to: 0 by: -1) asDigitsToPower: m do: [:digs | digs sum = n ifTrue: [results add: digs copy]].
^results

DouKaku?

自然数の分割

Posted feedbacks - Smalltalk

Index

Feed

Other

Link

Pathtraq