On 20 Nov 2017, at 10:33, Erling Hellenäs <[email protected]> wrote:
Hi all!
I made a comparison.
They are very similar in theirtime requirements, but Mike Days version uses
considerably less space.
This might be mainly due to the choice of ascii representation of theresult.
Some consequences of this choice:
x=:15
y=:15
x parMD y
0123456789:;<=>
x SetPartitionsGenerateF y
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
x=:255
y=:256
ts'x parMD y'
|index error: parMD
| list=.a {~list
ts'x SetPartitionsGenerateF y'
2.53384 1.73658e8
See below.
Cheers,
Erling Hellenäs
----Output---
x=:1
y=:1
EH=:(x SetPartitionsGenerateF y)</."1 i.y
MD=:(x parMD y) </."1 i.y
EH compare MD
1
x=:1
y=:2
EH=:(x SetPartitionsGenerateF y)</."1 i.y
MD=:(x parMD y) </."1 i.y
EH compare MD
1
x=:1
y=:3
EH=:(x SetPartitionsGenerateF y)</."1 i.y
MD=:(x parMD y) </."1 i.y
EH compare MD
1
x=:2
y=:4
EH=:(x SetPartitionsGenerateF y)</."1 i.y
MD=:(x parMD y) </."1 i.y
EH compare MD
1
x=:2
y=:5
EH=:(x SetPartitionsGenerateF y)</."1 i.y
MD=:(x parMD y) </."1 i.y
EH compare MD
1
x=:3
y=:5
EH=:(x SetPartitionsGenerateF y)</."1 i.y
MD=:(x parMD y) </."1 i.y
EH compare MD
1
x=:5
y=:10
ts'x SetPartitionsGenerateF y'
0.0217097 8.39974e6
ts'x parMD y'
0.0381484 796032
x=:6
y=:12
ts'x SetPartitionsGenerateF y'
1.03637 2.68448e8
ts'x parMD y'
1.06117 2.51788e7
---- Project ----
ts=: 6!:2 , 7!:2@] NB. Time and space
normalize=: 3 :0
NB. The idea here is to normalize the representation so that
NB. the copies are adjacent.
NB. Sort buckets within each combination after first item in each bucket
v31=.(] /: {.&.>)"1 y
NB. Sort buckets within each combination after number of items in each bucket
v4=.(] /: #&.>)"1 v31
NB. Sort
v5=. /:~ v4
(/: #&.> v5){ v5
)
compare=: -:&:normalize
NB. Mike Day
NB. produce a table of "restricted growth functions" (rgf) (strings of symbols)
subject to
NB. requirement that each "function" (or string) includes at least one instance
of each symbol
NB. eg 001100 is an rgf, but if all the symbols '012' are required, it's not
suitable here
NB. eg an rgf such as 001213 is a suitable equivalent to
NB. |01|24|3|5|, a 4-partition for 6 elements
NB. Any symbols may be used, but they are subject to an implicit or explicit
ordering.
parMD =: 3 : 0
y parMD~ <:#y
:
k =. <: x
NB. starting/current row
if. 1 = #y do.
list =. ,: cur =. (-y){.i.x
else. NB. Admit a starting row (of integers, not symbols) other than 0 0 0 1
2 ...
NB. NB. not tested here for validity!!!
list =. ,: cur =. y
end.
n =. #cur
a =. a. }.~ a. i. '0' NB. symbol list - arbitrary, but '012...' here
if. x > n do. NB. special-case impossible partitions
' '$~ 0, n
elseif. x = 1 do. NB. special-case 1-partition
,: n#{.a
elseif. x = 2 do. NB. special-case 2-partition
a{~ (n#2) #: }. i. 2 ^ n-1
elseif. x = n do. NB. special-case n-partition
,: n{.a
elseif. 1 do.
NB. I use the term k-partition, below, loosely - it should be x-partition or
(k+1)-partn.
list =. a {~ list NB. output as char array, offset so that 0 1 2 ... <==>
'012...'
NB. end =. k <. i. n NB. preset last row if required for stopping condition
incr =. =/~ i.n NB. look-up array for incrementing i{cur
blnk =. +/\ incr NB. look-up array for blanking all elements after i{cur
block=. x makeblock n NB. look-up array for forcing "new" rows to be
k-partition equivalents.
ki =. >:@i:&1@:(}. < k <. >:@:(>./\)@:}:) NB. restricted growth function
index finder,
NB. modified for limitation to
1+k symbols
while. n | i =. ki cur do. NB. test new index - stop if = n
NB. one of several possible stopping conditions - could
test cur -: end
new =. (i{incr) + cur*i{blnk NB. next suitable "restricted growth
function"
mx =. >./ new NB. ALL values 0 1 2 ... k MUST appear for a k-partition
NB. Adjust "new" if not already a k-partition equivalent, and expand to
several rows
new =. new +"1 >mx { block
NB. eg 00101000 (invalid k-part if x>2) becomes 00101023, 00101123 if (and
only if) x = 4
list =. list, new { a
cur =. {: new
end.
list
end.
)
NB. assemble look-up array of blocks
NB. eg
NB. 4 makeblock 5
NB. +---------+---------+---------+---------+
NB. |0 0 1 2 3|0 0 0 2 3|0 0 0 0 3|0 0 0 0 0|
NB. | |0 0 1 2 3|0 0 0 1 3|0 0 0 0 1|
NB. | | |0 0 0 2 3|0 0 0 0 2|
NB. | | | |0 0 0 0 3|
NB. +---------+---------+---------+---------+
makeblock =: 3 : 0
makeblock/ y
:
NB. a work-a-day method, not a smart implementation!
m =. 0
b =. ''
i =. i. x
while. x >: m =. >: m do.
b =. b, < (i.m),. m#,: i =. }. i
end.
(-y){."1 each b
)
NB. Erling Hellenäs
SetPartitionsGenerateF =: 4 : 0
NB. Generate all set partitions with k subsets from
NB. an original set with n unique items.
NB. x - number of subsets
NB. y - number of items in the set to partition
NB. Result - table of integers
NB. -each row is a generated set partition
NB. -columns contain the subset number of the items
NB. with the corresponding position in the set to
NB. partition.
NB. Algorithm from Frank Ruskey: Combinatorial Generation
NB. Working Version (1j-CSC 425/520).
(,: i.y) SPGF (x-1);y-1
)
SPGF =: 4 : 0
'k n' =. y
r=. (0,_1{.$x)$0
if. k=n do.
r=.x
else.
s=.n {."1 x
e=.(n+1)}."1 x
a=.,/s ( [,"1 1 (i.k+1),"0 1 ])"1 e
r=.r, a SPGF k;n-1
if. k > 0 do.
a=.s,.k,.e
r=.r, a SPGF (k-1);n-1
end.
end.
r
)
x=:1
y=:1
EH=:(x SetPartitionsGenerateF y)</."1 i.y
MD=:(x parMD y) </."1 i.y
EH compare MD
x=:1
y=:2
EH=:(x SetPartitionsGenerateF y)</."1 i.y
MD=:(x parMD y) </."1 i.y
EH compare MD
x=:1
y=:3
EH=:(x SetPartitionsGenerateF y)</."1 i.y
MD=:(x parMD y) </."1 i.y
EH compare MD
x=:2
y=:4
EH=:(x SetPartitionsGenerateF y)</."1 i.y
MD=:(x parMD y) </."1 i.y
EH compare MD
x=:2
y=:5
EH=:(x SetPartitionsGenerateF y)</."1 i.y
MD=:(x parMD y) </."1 i.y
EH compare MD
x=:3
y=:5
EH=:(x SetPartitionsGenerateF y)</."1 i.y
MD=:(x parMD y) </."1 i.y
EH compare MD
x=:5
y=:10
ts'x SetPartitionsGenerateF y'
ts'x parMD y'
x=:6
y=:12
ts'x SetPartitionsGenerateF y'
ts'x parMD y'
Den 2017-11-17 kl. 19:14, skrev '[email protected]' via Programming:
NB. produce a table of "restricted growth functions" (rgf) (strings of
symbols) subject to
NB. requirement that each "function" (or string) includes at least one
instance of each symbol
NB. eg 001100 is an rgf, but if all the symbols '012' are required,
it's not suitable here
NB. eg an rgf such as 001213 is a suitable equivalent to
NB. |01|24|3|5|, a 4-partition for 6 elements
NB. Any symbols may be used, but they are subject to an implicit or
explicit ordering.
parMD =: 3 : 0
y parMD~ <:#y
:
k =. <: x
NB. starting/current row
if. 1 = #y do.
list =. ,: cur =. (-y){.i.x
else. NB. Admit a starting row (of integers, not symbols) other than
0 0 0 1 2 ...
NB. NB. not tested here for validity!!!
list =. ,: cur =. y
end.
n =. #cur
a =. a. }.~ a. i. '0' NB. symbol list - arbitrary, but '012...'
here
if. x > n do. NB. special-case impossible partitions
' '$~ 0, n
elseif. x = 1 do. NB. special-case 1-partition
,: n#{.a
elseif. x = 2 do. NB. special-case 2-partition
a{~ (n#2) #: }. i. 2 ^ n-1
elseif. x = n do. NB. special-case n-partition
,: n{.a
elseif. 1 do.
NB. I use the term k-partition, below, loosely - it should be x-
partition or (k+1)-partn.
list =. a {~ list NB. output as char array, offset so that 0 1 2
... <==> '012...'
NB. end =. k <. i. n NB. preset last row if required for stopping
condition
incr =. =/~ i.n NB. look-up array for incrementing i{cur
blnk =. +/\ incr NB. look-up array for blanking all elements
after i{cur
block=. x makeblock n NB. look-up array for forcing "new" rows to be k-
partition equivalents.
ki =. >:@i:&1@:(}. < k <. >:@:(>./\)@:}:) NB. restricted growth
function index finder,
NB. modified for
limitation to 1+k symbols
while. n | i =. ki cur do. NB. test new index - stop if = n
NB. one of several possible stopping conditions -
could test cur -: end
new =. (i{incr) + cur*i{blnk NB. next suitable "restricted growth
function"
mx =. >./ new NB. ALL values 0 1 2 ... k MUST appear for a k-
partition
NB. Adjust "new" if not already a k-partition equivalent, and expand
to several rows
new =. new +"1 >mx { block
NB. eg 00101000 (invalid k-part if x>2) becomes 00101023, 00101123 if
(and only if) x = 4
list =. list, new { a
cur =. {: new
end.
list
end.
)
NB. assemble look-up array of blocks
NB. eg
NB. 4 makeblock 5
NB. +---------+---------+---------+---------+
NB. |0 0 1 2 3|0 0 0 2 3|0 0 0 0 3|0 0 0 0 0|
NB. | |0 0 1 2 3|0 0 0 1 3|0 0 0 0 1|
NB. | | |0 0 0 2 3|0 0 0 0 2|
NB. | | | |0 0 0 0 3|
NB. +---------+---------+---------+---------+
makeblock =: 3 : 0
makeblock/ y
:
NB. a work-a-day method, not a smart implementation!
m =. 0
b =. ''
i =. i. x
while. x >: m =. >: m do.
b =. b, < (i.m),. m#,: i =. }. i
end.
(-y){."1 each b
)
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
