Here's a recursive implementation.
tree =: ({.,<@$:@;@}.)"1@(({.;}.)S:0,.1[\.])^:(0<#)@(</.~)
paths =: ({. ,"0 1 L:0 ($:L:_1)@}.)`;@.(L.=1:)"1
extract =: ,S:0
dupermu =: extract@:paths@tree
tree 1 1 2 2
┌─┬────────────┐
│1│┌─┬────────┐│
│ ││1│┌─┬────┐││
│ ││ ││2│┌─┬┐│││
│ ││ ││ ││2│││││
│ ││ ││ │└─┴┘│││
│ ││ │└─┴────┘││
│ │├─┼────────┤│
│ ││2│┌─┬────┐││
│ ││ ││2│┌─┬┐│││
│ ││ ││ ││1│││││
│ ││ ││ │└─┴┘│││
│ ││ │├─┼────┤││
│ ││ ││1│┌─┬┐│││
│ ││ ││ ││2│││││
│ ││ ││ │└─┴┘│││
│ ││ │└─┴────┘││
│ │└─┴────────┘│
├─┼────────────┤
│2│┌─┬────────┐│
│ ││2│┌─┬────┐││
│ ││ ││1│┌─┬┐│││
│ ││ ││ ││1│││││
│ ││ ││ │└─┴┘│││
│ ││ │└─┴────┘││
│ │├─┼────────┤│
│ ││1│┌─┬────┐││
│ ││ ││1│┌─┬┐│││
│ ││ ││ ││2│││││
│ ││ ││ │└─┴┘│││
│ ││ │├─┼────┤││
│ ││ ││2│┌─┬┐│││
│ ││ ││ ││1│││││
│ ││ ││ │└─┴┘│││
│ ││ │└─┴────┘││
│ │└─┴────────┘│
└─┴────────────┘
paths @ tree 1 1 2 2
┌───────────┐
│┌─────────┐│
││┌───────┐││
│││1 1 2 2│││
││└───────┘││
│├─────────┤│
││┌───────┐││
│││1 2 2 1│││
││├───────┤││
│││1 2 1 2│││
││└───────┘││
│└─────────┘│
├───────────┤
│┌─────────┐│
││┌───────┐││
│││2 2 1 1│││
││└───────┘││
│├─────────┤│
││┌───────┐││
│││2 1 1 2│││
││├───────┤││
│││2 1 2 1│││
││└───────┘││
│└─────────┘│
└───────────┘
extract @: paths @ tree 1 1 2 2
1 1 2 2
1 2 2 1
1 2 1 2
2 2 1 1
2 1 1 2
2 1 2 1
It's quite a bit slower and bulkier than your version:
timespacex 'rperm #~ 1 2 3 4'
0.0866179 1.05582e7
timespacex 'tree #~ 1 2 3 4'
1.03336 1.14867e7
timespacex 'paths@tree #~ 1 2 3 4'
1.43226 1.88212e7
timespacex 'extract@:paths@tree #~ 1 2 3 4'
1.4384 2.27409e7
I feel like there should be a way to get the flattened answer directly in a
verb like "tree" without building the giant nested array, but I haven't
figured out how to make it happen yet.
On Fri, Apr 24, 2015 at 3:00 PM, 'Pascal Jasmin' via Programming <
programm...@jsoftware.com> 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
