Nice, Raul. Very fast too.
There is one big advantage to my approach in that the outer loop is a useful
incremental function
perm =: i.@! A. i.
incrperm =: 4 : 0
map =. x ~: y
o =. x ,"1 y
for_j. i. {: $ map do. o =. o , (>:j) (x insertpos)"1 y #~ j{"1 map end.
~. o
)
NB. redefined as single line.
incrperm =: 4 : ' map =. x ~: y [ o =. x ,"1 y for_j. i. {: $ map do. o =. o
, (>:j) ({. , x , }.)"1 y #~ j{"1 map end. ~. o '
NB. for some reason faster with xtras temporary variable
rperm2 =: 3 : ' p =. ({~ [: perm #) ~. y [ xtras=. ; }. each </.~ y for_i.
xtras do. p =. i incrperm p end.'
reducE =: 1 : (':'; 'o=. x for_i. y do. o =. o u i end.')
NB. same as rperm2
rperm3 =: 3 : '( ({~ [: perm #) ~. y) incrperm~ reducE ; }. each </.~ y'
what incrperm does is "shuffle in" one extra item into an existing list of
permutations
(rperm2 1 1 2 2) -: 2 incrperm rperm2 1 1 2
1
from the style of rperm3, you can shuffle in multiple items as:
2 2 incrperm~ reducE~ rperm2 1 1 2
2 2 1 1 2
2 2 1 2 1
2 2 2 1 1
2 1 2 1 2
2 1 2 2 1
2 1 1 2 2
1 2 2 1 2
1 2 2 2 1
1 2 1 2 2
1 1 2 2 2
The main use case is to filter out permutations as you grow the list,
preventing a "combinatoric explosion" (or trying to). Usually, you are
creating these permutations as part of a greater search problem, and so using a
scoring function can probably eliminate several as you go along, or just sort
and keep searching through a manageable number.
----- Original Message -----
From: Raul Miller <[email protected]>
To: Programming forum <[email protected]>
Cc:
Sent: Saturday, April 25, 2015 1:46 AM
Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
On Fri, Apr 24, 2015 at 7:03 PM, Roger Hui <[email protected]> wrote:
> The details of implementing this algorithm are left as an exercise for the
> reader. :-)
Do I qualify as a reader?
comb=: 4 : 0
k=. i.>:d=.y-x
z=. (d$<i.0 0),<i.1 0
for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
; z
)
peermm=:3 :0
r=.i.1 0
for_d.</.~y do.
u=.{.s=.>d
n=.i.(#s)+{:$r
e=.n e."1 s comb&#n
r=.,/(u*e)+"1/"_1 (1-e)#inv"1/r
end.
)
peermm 1 1 2 2
2 2 1 1
2 1 2 1
2 1 1 2
1 2 2 1
1 2 1 2
1 1 2 2
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
