First permC can be sped up by removing 1s from factorial of right hand side
permC =: (# %&((*/))&:(!@x:) 1 -.~ #/.~)
this gets at least 20% or so consistent speed improvement
permC2 =: (] ((] + >:@i.@((-~ +/)~)) ([ ({."1@[ */@:^&x:
(-/@:,:)&:({:"1))&:(~. ,. #/.~)&:(/:~)&(;@:(q: each)) ;@:((2 + i.@<:)
each)@:]) 1 -.~ -.) >./)@:(#/.~)
an easier to follow model of permC2 through more linear code. Basically the q:
of each side's digits are taken, and consolidated into the q: exponent table
format. Each side is guaranteed to have at least 1 copy of every consecutive
prime (with right side having fewer primes than left), and so the exponents can
just be subtracted.
(({."1 every@:{.) */@:^&x: -/@:({:"1 every)) (~. ,. #/.~) each /:~@:;@:(q:
each) each ((2 + i.@<:)@:(+/) ; ;@:((2 + i.@<:) each)) 8 8 8 1 2 3 1 1 1 13
1123431404579781579567208123200000
timespacex 'permC (] # i.@#) 133 122'
0.000542399 94208
timespacex 'permC2 (] # i.@#) 133 122'
0.00020096 70912
20 timespacex '(# !~ x:@{.@(#/.~)) (] # i.@#) 133 122'
7.62079e_5 112512
The last example takes advantage of calculating boolean list permutations is
the same formula as dyadic !. Its 3x faster, even after converting back from
list format, and suggests another possible technique to extend to 3 +
classifications as repeated application of the boolean/combination formula.
items are 0 or not 0, then for those not 0, are 1 or 2.
permC3 =: */@:({. ! +/)\.@:x:@:(#/.~)
this is faster as long as there is a reasonable number of "classifications"
with relatively high frequencies
20 timespacex 'permC3 (] # i.@#) 133 122 77 55 22 88'
0.00040688 202624
20 timespacex 'permC2 (] # i.@#) 133 122 77 55 22 88'
0.000535343 194688
20 timespacex 'permC3 (] # i.@#) 133 122 77 55 22 88 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1'
0.000709327 213120
20 timespacex 'permC2 (] # i.@#) 133 122 77 55 22 88 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1'
0.000590591 208000
----- Original Message -----
From: 'Pascal Jasmin' via Programming <[email protected]>
To: Programming Forum <[email protected]>
Sent: Monday, May 9, 2016 11:10 AM
Subject: [Jprogramming] challenge: optimizing permutations with repeat count
permC =: (# %&((*/))&:(!@x:) #/.~)
this takes a list as argument, and the innerverb takes the factorials of the
count, and divides with the product of the factorials of item frequencies.
I notice that there is not much difference between these 2 functions:
20 timespacex '*/ 2 + i. <: 500x'
0.000897903 156928
20 timespacex '!500x'
0.000890463 88448
The permutation count of a list is guaranteed to be an integer which means that
every single term on the right hand side is combinable into a term that exists
on the left hand side.
permC 8 # 0 1 2
9465511770
the left and right product lists,
((2 + i.@<:) 24) ; ;@:((2 + i.@<:) each) 8 8 8
so find f such that,
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 f 2 3 4 5 6 7 8 2
3 4 5 6 7 8 2 3 4 5 6 7 8
is faster than permC, likely resulting in no division step.
One quick optimization may be: (removing largest frequency from left hand side)
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 f 2 3 4 5 6 7 8 2 3 4 5 6 7 8
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
