As an exercise on ZDD programming, I have written a small codes, which enumerates all partitions for a given small natural number n. It is a naive and toy codes, but unexpectedly, turns out to enumerate all partitions for 100 correctly.
EDIT: I just remember that the partition number function p(n) has a property
of easy recurrence relation which leads to compute p(n) efficiently by “course of values” induction. So it might not be interesting for prologers to compute p(n) directly.
?- time(zdd((partition_number(100, X), card(X, C)))).
% 108,772,104,054 inferences, 13710.178 CPU in 13730.088 seconds (100% CPU, 7933676 Lips)
X = 291521,
C = 190569292.
( see http://www.numericana.com/data/partition.htm )
As I did this just as a hobby exercise, I have no idea what this experiment suggests, but would like to know about existing prolog codes on such enumerating partitions. There should have been clever and efficient prolog codes on such famous problem.
This is main part of source codes:
partition_number(N, X):- shift0(partition_number(N, X)).
%
partition_number(N, X, S):- partition_number(N, 1, X, S).
%
partition_number(0, X, X, _):-!.
partition_number(I, X, Y, S):-
partition_number_step(X, Y0, S),
J is I - 1,
partition_number(J, Y0, Y, S).
%
partition_number_step(X, Y):- shift0(partition_number_step(X, Y)).
%
partition_number_step(I, J, S):- update_keyval(1-1, I, I0, S),
recursive_update_top_keyval(I, J0, S),
zdd_join(I0, J0, J, S).
%
recursive_update_top_keyval(I, 0, _):- I < 2, !.
recursive_update_top_keyval(I, J, S):- cofact(I, t(X, L, R), S),
recursive_update_top_keyval(L, L0, S),
update_top_keyval(X, R, U, S),
recursive_update_top_keyval(R, V, S),
zdd_insert(X, V, W, S),
zdd_join_list([L0, U], W, J, S).
update_keyval(X, Y, Z):- shift0(update_keyval(X, Y, Z)).
%
update_keyval(_, 0, 0, _):-!.
update_keyval(_-0, I, I, _):-!.
update_keyval(A, 1, J, S):-!, zdd_singleton(A, J, S).
update_keyval(A, I, J, S):- A = KeyA-ValA,
memo(update_keyval(A, I)-J, S),
( nonvar(J) -> true % , write(.) % Many hits.
; cofact(I, t(X, L, R), S),
X = KeyX-ValX,
update_keyval(A, L, L0, S),
compare(C, KeyA, KeyX),
( C = (=) ->
NewVal is ValX + ValA,
insert_join(KeyX-NewVal, L0, R, J, S)
; C = (<) -> cofact(J, t(A, 0, I), S)
; update_keyval(A, R, R0, S),
insert_join(X, L0, R0, J, S)
)
).
%
insert_join(A, L, R, U, S):- zdd_insert(A, R, R0, S),
zdd_join(L, R0, U, S).
%
update_top_keyval(X, Y):- shift0(update_top_keyval(X, Y)).
%
update_top_keyval(I, 0, _):- I<2, !.
update_top_keyval(I, J, S):-
cofact(I, t(X, L, R), S),
update_top_keyval(L, L0, S),
update_top_keyval(X, R, R0, S),
zdd_join(L0, R0, J, S).
%
update_top_keyval(X, I, J, S):- memo(top_keyval(X, I)-J, S),
( nonvar(J) -> true % , write(.) % Many hits.
; X = Key-Val,
K is Key+1,
V is Val-1,
update_keyval(K-1, I, I0, S),
update_keyval(Key-V, I0, J, S)
).
EDIT: I wrote another codes on the partition number functions
without enumerating all patitions in ZDD of a given number,
but directly with recursion, using the hash functions in my ZDD library. The codes looks much like the well known Fibonacci series computation using the table/1 directive. The original post was to report on enumaration of all partions in ZDD for a given particular small number, but it was very fresh to me to remind that the partition number functions itself is a function which can be computed very fast like the Fibonacci function, as tested below. I am afraid that I am added what is popular among prologers.
% ?- time(zdd((repeat(1-100, I, (pn(I, P), writeln(pn(I)=P)))))).
%@ pn(1)=1
%@ pn(2)=2
%@ pn(3)=3
%@ pn(4)=5
%@ pn(5)=7
%@ pn(6)=11
%@ pn(7)=15
%@ pn(8)=22
%@ pn(9)=30
%@ pn(10)=42
%@ pn(11)=56
%@ pn(12)=77
%@ pn(13)=101
%@ pn(14)=135
%@ pn(15)=176
%@ pn(16)=231
%@ pn(17)=297
%@ pn(18)=385
%@ pn(19)=490
%@ pn(20)=627
%@ pn(21)=792
%@ pn(22)=1002
%@ pn(23)=1255
%@ pn(24)=1575
%@ pn(25)=1958
%@ pn(26)=2436
%@ pn(27)=3010
%@ pn(28)=3718
%@ pn(29)=4565
%@ pn(30)=5604
%@ pn(31)=6842
%@ pn(32)=8349
%@ pn(33)=10143
%@ pn(34)=12310
%@ pn(35)=14883
%@ pn(36)=17977
%@ pn(37)=21637
%@ pn(38)=26015
%@ pn(39)=31185
%@ pn(40)=37338
%@ pn(41)=44583
%@ pn(42)=53174
%@ pn(43)=63261
%@ pn(44)=75175
%@ pn(45)=89134
%@ pn(46)=105558
%@ pn(47)=124754
%@ pn(48)=147273
%@ pn(49)=173525
%@ pn(50)=204226
%@ pn(51)=239943
%@ pn(52)=281589
%@ pn(53)=329931
%@ pn(54)=386155
%@ pn(55)=451276
%@ pn(56)=526823
%@ pn(57)=614154
%@ pn(58)=715220
%@ pn(59)=831820
%@ pn(60)=966467
%@ pn(61)=1121505
%@ pn(62)=1300156
%@ pn(63)=1505499
%@ pn(64)=1741630
%@ pn(65)=2012558
%@ pn(66)=2323520
%@ pn(67)=2679689
%@ pn(68)=3087735
%@ pn(69)=3554345
%@ pn(70)=4087968
%@ pn(71)=4697205
%@ pn(72)=5392783
%@ pn(73)=6185689
%@ pn(74)=7089500
%@ pn(75)=8118264
%@ pn(76)=9289091
%@ pn(77)=10619863
%@ pn(78)=12132164
%@ pn(79)=13848650
%@ pn(80)=15796476
%@ pn(81)=18004327
%@ pn(82)=20506255
%@ pn(83)=23338469
%@ pn(84)=26543660
%@ pn(85)=30167357
%@ pn(86)=34262962
%@ pn(87)=38887673
%@ pn(88)=44108109
%@ pn(89)=49995925
%@ pn(90)=56634173
%@ pn(91)=64112359
%@ pn(92)=72533807
%@ pn(93)=82010177
%@ pn(94)=92669720
%@ pn(95)=104651419
%@ pn(96)=118114304
%@ pn(97)=133230930
%@ pn(98)=150198136
%@ pn(99)=169229875
%@ pn(100)=190569292
%@ % 809,149 inferences, 0.081 CPU in 0.081 seconds (99% CPU, 10018312 Lips)
%@ true.
parity(J, S):- % S is power of -1 by J: S = (-1)^ J.
( J mod 2 =:= 0 -> S = 1
; S = -1
).
jm(J, X):- X is (J*(3*J-1)) //2.
jp(J, X):- X is (J*(3*J+1)) //2.
pn(P, N):- shift0(pn(P, N)).
pn(N, 0, _):- N<0, !.
pn(0, 1, _):-!.
pn(1, 1, _):-!.
pn(N, P, S):- memo(pn(N)-P, S),
( nonvar(P) -> true
; pn_sum(N, 1, 0, P0, S),
P is -P0
).
%
pn_sum(N, J, A, B, S):-
jm(J, Jm),
jp(J, Jp),
Nm is N-Jm,
Np is N-Jp,
( Nm < 0 -> B = A
; parity(J, P),
pn(Nm, U0, S),
pn(Np, V0, S),
A0 is A + P*(U0+V0),
J0 is J + 1,
pn_sum(N, J0, A0, B, S)
).
Kuniaki Mukai