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
