Hi all !
I have a new and different parE that is slightly better than parELMDE.
parE=: 4 : 0
NB. Assume a table with x rows and y columns.
NB. Each row is a bucket, each column an item.
NB. Two buckets can not contain the same item.
NB. This means there can only be one item in each column.
NB. Each column can be rotated in x ways.
NB. Generate all combinations of the possible rotations
NB. except for the first x columns.
NB. o=:(y#x)#:i.x^y
o=:iy#:i.*/iy=:(1+i.x),(y-x)$x
NB. Pick the rotation from a bitmap where each
NB. row is a possible rotation
NB. We now have a three-dimensional bitmap of
NB. combination, items in the bucket and bucket
NB. True means the bucket contains the corresponding item
v=:o{(i.x)|."0 1 x{.1
NB. Select the combination where each bucket contains at least
NB. one item.
b=:(*./"1+./"2 v)#v
NB. Reorder the dimensions
NB. Now they are combination, bucket and items in the bucket.
c=:0 2 1|:b
NB. Sort the buckets within the combinations so that
NB. buckets with the same contents also are in the same place
NB. in bucket order
d=:/:~"2 c
NB. Remove duplicates
e=: ~.d
NB. Display
e<@# i.y
)
x=:5
y=:11
(x parE y)compare x parELMDE y
1
ts'x parE y'
1.55969 3.32636e8
ts'x parELMDE y'
1.79359 8.38865e8
Cheers,
Erling Hellenäs
Den 2017-10-31 kl. 20:17, skrev 'Mike Day' via Programming:
Thanks, Raul.
NB - mods to parRuskey below!
I'm not sure my latest effort (mdconst) merits much study.
If you do look, you might notice that the filtering check can be done
slightly more
efficiently by building only the first column of the new comparand and
then constructing
all columns only for required rows, but at the cost of greater code
complexity and even less
transparency. Congrats if you understand this!
Erling might like to look at this modification of his own recent
amended version of parRuskey.
It manages to avoid some recursion. The calling routine is as he
posted earlier today,
but I'll reproduce it here, with subscripts "new" for it and for the
"S" verb:
parRuskeynew =: 4 : 0
NB. L =: 0$~0, 2 + y NB. debug/understand array of call parameters
r=. (i.y) Snew (x-1),y-1
NB. R =: r NB. debug/understand output
r </."1 i.y
)
Snew =: 4 : 0
NB. L =: L, y, x NB. debug/understand array of call parameters
'k n' =. y
a =.x
r =. 0$~ 0, #a
if. k = n - 1 do. NB. replace repeated calls with k = n (on entry)
r =. (i.k+1) n }"0 1 (k+1)# ,:a NB. don't need to use recursion here!
else.
NB. is there a way to avoid recursion here, too?
r =. r, ,/ (Snew&(k,n-1))"1 (i.k+1) n }"0 1 a NB.apply "1 instead of
do loop
end.
if. k > 0 do.
r=.r, (k n } a) Snew (k-1),n-1
end.
r
)
(parRuskeynew -:parRuskey) /6 9
1
Getting more J-ish?
Cheers,
Mike
On 31/10/2017 16:31, Raul Miller wrote:
Well... I did get as far as doing basic timings:
tim=:2 :0
:
u ratetime v"0
)
ratetime=:2 :0
u NB. force x and y to be verb args
:
try.
assert. x<:y
tV=.6!:2 'rV=. x v y'
tU=.6!:2 'rU=. x u y'
tU%tV
catch.
rV=.rU=.0
_
end.
assert. rV -:&(/:~)&:(/:~"1)&:(/:~&.>) rU
)
9!:11]2 NB. shrink precision to be more social
G=:parRDM tim mdconst
(1+i.10) G table 1+i.10
┌──┬─────────────────────────────────────────────────┐
│G │ 1 2 3 4 5 6 7 8 9 10│
├──┼─────────────────────────────────────────────────┤
│ 1│0.58 0.8 1 0.67 1 0.67 1.5 0.67 1.5 0.67│
│ 2│ _ 2.7 0.15 0.14 0.22 0.21 0.29 0.23 0.42 0.45│
│ 3│ _ _ 0.83 1 1.3 1.3 0.72 1.1 1.1 0.99│
│ 4│ _ _ _ 0.8 0.85 1.2 1.2 1 1.2 1.2│
│ 5│ _ _ _ _ 0.89 0.74 0.93 1.1 1.2 1│
│ 6│ _ _ _ _ _ 0.9 0.53 0.59 0.73 0.83│
│ 7│ _ _ _ _ _ _ 0.91 0.33 0.27 0.53│
│ 8│ _ _ _ _ _ _ _ 0.83 0.17 0.16│
│ 9│ _ _ _ _ _ _ _ _ 0.78 0.082│
│10│ _ _ _ _ _ _ _ _ _ 0.75│
└──┴─────────────────────────────────────────────────┘
(Beware proportionally spaced fonts: they are messy...)
parRDM from
http://jsoftware.com/pipermail/programming/2017-October/049451.html
mdconst from
http://jsoftware.com/pipermail/programming/2017-October/049453.html
I did sort of like the idea of pre-computing partition sizes and
building up from there, But I have not deeply studied your code yet.
(It is on my todo list, though...)
Thanks,
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
