I haven't quite used all of these ideas, but did use the first. And insert one
item at a time into the previously built permutations. That is the critical
part of any approach. Even though I add slightly too many items, and need to
clean up with ~. on each pass, it at least doesn't build up a barely-countable
number of lists.
perm =: i.@! A. i.
NB. insert m at position x in y
insertpos =: 1 : '{. , m , }.'
NB. repeat permutations. y is item list with repeats
rperm =: 3 : 0
p =. ({~ [: perm #) ~. y
xtras =. ; }. each <@,/.~ y
for_i. xtras do.
map =. i ~: p
o =. i ,"1 p
for_j. i. {: $ map do. o =. o , (>:j) (i insertpos)"1 p #~ j{"1 map end.
p =. ~. o
end.
)
to make this many permutations
(!12) % */ ! #/.~ 2 2 7 7 8 8 9 9 9 9 9 9
83160
without this many from A.
!12
4.79002e8
timespacex '# rperm 2 2 7 7 8 8 9 9 9 9 9 9 '
0.54311 9.28059e7
----- Original Message -----
From: Roger Hui <[email protected]>
To: Programming forum <[email protected]>
Cc:
Sent: Friday, April 24, 2015 7:03 PM
Subject: Re: [Jprogramming] Permutations with repeats (combinations?)
The "secret" is to avoid generating duplicates which are then removed.
Partition the argument into a collection of like elements:
</.~ 0 1 2 2
┌─┬─┬───┐
│0│1│2 2│
└─┴─┴───┘
Suppose you already have a matrix m of the "permutation with repeats" for
the first two elements.
m
0 1
1 0
To include the next set of elements s (the 2 2 in this case), the resultant
matrix z would have 4 columns. Rows of z are distinguished by which
columns would have s. The possible columns are (#s) comb (#s)+{:$m:
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
)
(#s) comb (#s)+{:$m
0 1
0 2
0 3
1 2
1 3
2 3
From these column indices generate the z:
0 1 2 2 0 1
2 2 1 0
0 2 2 0 2 1
2 1 2 0
0 3 2 0 1 2
2 1 0 2
1 2 0 2 2 1
1 2 2 0
1 3 0 2 1 2
1 2 0 2
2 3 0 1 2 2
1 0 2 2
The procedure generalizes if the there are no duplicates, resulting in the
ordinary matrix of permutations.
The details of implementing this algorithm are left as an exercise for the
reader. :-)
On Fri, Apr 24, 2015 at 1:00 PM, 'Pascal Jasmin' via Programming <
[email protected]> wrote:
> archive or wiki did not help, but perhaps I searched wrong
>
> perm =: i.@! A. i.
>
> ~.@({~ [: perm #) 1 1 2 2
> 1 1 2 2
> 1 2 1 2
> 1 2 2 1
> 2 1 1 2
> 2 1 2 1
> 2 2 1 1
>
> while that is the answer I want, and is short and elegant, it grows very
> innefficient as the length of the argument grows even if the answer is a
> short list.
>
> Is there an algorithm that can produce these "permutations with repeats"
> without the intermediate full permutation list?
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
