Hi all!
I created a program for enumeration of multiset permutations. It could
possibly be used to answer the Quora question.
Comments are welcome.
Display=: 4 : ' x { ~. y'
N=: ,2 1
y=: ,6 6 7
MultisetPermutationsEnumerate N
0 0 1
0 1 0
1 0 0
(MultisetPermutationsEnumerate N )Display y
6 6 7
6 7 6
7 6 6
------Project------------
MultisetPermutationsEnumerate =: 3 : 0
NB. Enumerate multiset or bag permutations.
NB. y - vector with number of repetitions.
NB. Result - table of permutations - indexes in the nub
NB. of the multiset.
NB. Algorithm from Frank Ruskey: Combinatorial Generation
NB. Working Version (1j-CSC 425/520).
p=.(+/y)#0
'r p N'=. (p;y) MPERec <:#p
|."1 r
)
MPERec =: 4 : 0
'p N'=.x
if. (0{N) = >:y do.
r=.,:p
else.
r=. (0,#p)$0
for_j. (N>0)#i.#N do.
p=. j y } p
N=. (<:j{N) j } N
't p N'=. (p;N) MPERec <:y
r=.r,t
N=. (>:j{N) j } N
p=.0 y }p
end.
end.
r;p;N
)
Display=: 4 : ' x { ~. y'
log=: ,.<i.0
N=: ,1
y=: ,6
MultisetPermutationsEnumerate N
(MultisetPermutationsEnumerate N )Display y
log=: ,.<i.0
N=: ,1 1
y=: ,6 7
MultisetPermutationsEnumerate N
( MultisetPermutationsEnumerate N )Display y
N=: ,2 1
y=: ,6 6 7
MultisetPermutationsEnumerate N
(MultisetPermutationsEnumerate N )Display y
N=: ,2 1 1
y=: ,6 6 7 8
MultisetPermutationsEnumerate N
(MultisetPermutationsEnumerate N )Display y
N=: ,1 2 1
y=: ,7 6 6 8
MultisetPermutationsEnumerate N
(MultisetPermutationsEnumerate N )Display y
---Output----
log=: ,.<i.0
N=: ,1
y=: ,6
MultisetPermutationsEnumerate N
0
(MultisetPermutationsEnumerate N )Display y
6
log=: ,.<i.0
N=: ,1 1
y=: ,6 7
MultisetPermutationsEnumerate N
0 1
1 0
( MultisetPermutationsEnumerate N )Display y
6 7
7 6
N=: ,2 1
y=: ,6 6 7
MultisetPermutationsEnumerate N
0 0 1
0 1 0
1 0 0
(MultisetPermutationsEnumerate N )Display y
6 6 7
6 7 6
7 6 6
N=: ,2 1 1
y=: ,6 6 7 8
MultisetPermutationsEnumerate N
0 0 1 2
0 0 2 1
0 1 0 2
0 1 2 0
0 2 0 1
0 2 1 0
1 0 0 2
1 0 2 0
1 2 0 0
2 0 0 1
2 0 1 0
2 1 0 0
(MultisetPermutationsEnumerate N )Display y
6 6 7 8
6 6 8 7
6 7 6 8
6 7 8 6
6 8 6 7
6 8 7 6
7 6 6 8
7 6 8 6
7 8 6 6
8 6 6 7
8 6 7 6
8 7 6 6
N=: ,1 2 1
y=: ,7 6 6 8
MultisetPermutationsEnumerate N
0 1 1 2
0 1 2 1
0 2 1 1
1 0 1 2
1 0 2 1
1 1 0 2
1 1 2 0
1 2 0 1
1 2 1 0
2 0 1 1
2 1 0 1
2 1 1 0
(MultisetPermutationsEnumerate N )Display y
7 6 6 8
7 6 8 6
7 8 6 6
6 7 6 8
6 7 8 6
6 6 7 8
6 6 8 7
6 8 7 6
6 8 6 7
8 7 6 6
8 6 7 6
8 6 6 7
Cheers,
Erling Hellenäs
Den 2017-11-06 kl. 14:21, skrev Erling Hellenäs:
Hi all!
Do we have a program or built-in function to enumerate the
permutations of multisets, sets with item repetitions?
Cheers,
Erling Hellenäs
Den 2017-11-06 kl. 10:37, skrev Linda Alvord:
This is handier when there are more sets of repetions.
(!6)%(!2)*!2
180
/
(!6)%*/!2 2
180
Linda
-----Original Message-----
From: Programming [mailto:[email protected]]
On Behalf Of Erling Hellenäs
Sent: Sunday, November 5, 2017 11:28 AM
To: [email protected]
Subject: Re: [Jprogramming] Partitions
Hi all!
Even though this solution is only relevant as an answer to the Quora
question, I want to post a correction.
Since there can be duplicates in the root sets, there is not always
!n permutations.
The formula is here:
https://brilliant.org/wiki/permutations-with-repetition/
The corrected list:
list=:4 : 0
v=.((x-1)#1),q: y
r1=.x parRuskeyE #v
r2=. >r1 (*/)@:{&.>"1 0 < v
r3=./:~"1 r2
r4=. ~.r3
perm=.3 : '(!#y)%*/!+/y=/~.y'
r5=.perm"1 r4
+/r5
)
Test output:
v=: ((x-1)#1),q:u=:2*2*3*3
r1=:3 parRuskeyE #v
r2=: >r1 (*/)@:{&.>"1 0 < v
r3=:/:~"1 r2
[r4=: ~.r3
1 2 18
2 2 9
1 4 9
2 3 6
3 3 4
1 6 6
1 3 12
1 1 36
*./u =*/"1 r4
1
perm=: 3 : '(!#y)%*/!+/y=/~.y'
[r5=:perm"1 r4
6 3 6 6 3 3 6 3
[+/r5
36
3 list 2*2*3*3
36
perm 1 2 3 3
12
(!4)%!2
12
perm 1 2 3 3 5 5
180
(!6)%(!2)*!2
180
Cheers,
Erling Hellenäs
On 2017-11-03 18:24, Erling Hellenäs wrote:
Hi all!
list=:4 : 0
v=.((x-1)#1),q: y
r1=.x parRuskeyE #v
r2=. >r1 (*/)@:{&.>"1 0 < v
r3=./:~"1 r2
r4=. ~.r3
(!x)*#r4
)
3 list 24
36
Cheers,
Erling Hellenäs
On 2017-11-03 17:36, Erling Hellenäs wrote:
Hi all !
Below is the output of the run on the Quora question.
Maybe someone can see if there is a problem.
Cheers,
Erling Hellenäs
[v=: 1 1 ,q:24
1 1 2 2 2 3
[r=:3 parRuskeyE #v
┌───────┬───────┬───────┐
│0 3 4 5│1 │2 │
├───────┼───────┼───────┤
│0 4 5 │1 3 │2 │
├───────┼───────┼───────┤
│0 4 5 │1 │2 3 │
├───────┼───────┼───────┤
│0 3 5 │1 4 │2 │
├───────┼───────┼───────┤
│0 5 │1 3 4 │2 │
├───────┼───────┼───────┤
│0 5 │1 4 │2 3 │
├───────┼───────┼───────┤
│0 3 5 │1 │2 4 │
├───────┼───────┼───────┤
│0 5 │1 3 │2 4 │
├───────┼───────┼───────┤
│0 5 │1 │2 3 4 │
├───────┼───────┼───────┤
│0 3 4 │1 5 │2 │
├───────┼───────┼───────┤
│0 4 │1 3 5 │2 │
├───────┼───────┼───────┤
│0 4 │1 5 │2 3 │
├───────┼───────┼───────┤
│0 3 │1 4 5 │2 │
├───────┼───────┼───────┤
│0 │1 3 4 5│2 │
├───────┼───────┼───────┤
│0 │1 4 5 │2 3 │
├───────┼───────┼───────┤
│0 3 │1 5 │2 4 │
├───────┼───────┼───────┤
│0 │1 3 5 │2 4 │
├───────┼───────┼───────┤
│0 │1 5 │2 3 4 │
├───────┼───────┼───────┤
│0 3 4 │1 │2 5 │
├───────┼───────┼───────┤
│0 4 │1 3 │2 5 │
├───────┼───────┼───────┤
│0 4 │1 │2 3 5 │
├───────┼───────┼───────┤
│0 3 │1 4 │2 5 │
├───────┼───────┼───────┤
│0 │1 3 4 │2 5 │
├───────┼───────┼───────┤
│0 │1 4 │2 3 5 │
├───────┼───────┼───────┤
│0 3 │1 │2 4 5 │
├───────┼───────┼───────┤
│0 │1 3 │2 4 5 │
├───────┼───────┼───────┤
│0 │1 │2 3 4 5│
├───────┼───────┼───────┤
│0 2 4 5│1 │3 │
├───────┼───────┼───────┤
│0 4 5 │1 2 │3 │
├───────┼───────┼───────┤
│0 2 5 │1 4 │3 │
├───────┼───────┼───────┤
│0 5 │1 2 4 │3 │
├───────┼───────┼───────┤
│0 2 5 │1 │3 4 │
├───────┼───────┼───────┤
│0 5 │1 2 │3 4 │
├───────┼───────┼───────┤
│0 2 4 │1 5 │3 │
├───────┼───────┼───────┤
│0 4 │1 2 5 │3 │
├───────┼───────┼───────┤
│0 2 │1 4 5 │3 │
├───────┼───────┼───────┤
│0 │1 2 4 5│3 │
├───────┼───────┼───────┤
│0 2 │1 5 │3 4 │
├───────┼───────┼───────┤
│0 │1 2 5 │3 4 │
├───────┼───────┼───────┤
│0 2 4 │1 │3 5 │
├───────┼───────┼───────┤
│0 4 │1 2 │3 5 │
├───────┼───────┼───────┤
│0 2 │1 4 │3 5 │
├───────┼───────┼───────┤
│0 │1 2 4 │3 5 │
├───────┼───────┼───────┤
│0 2 │1 │3 4 5 │
├───────┼───────┼───────┤
│0 │1 2 │3 4 5 │
├───────┼───────┼───────┤
│0 1 4 5│2 │3 │
├───────┼───────┼───────┤
│0 1 5 │2 4 │3 │
├───────┼───────┼───────┤
│0 1 5 │2 │3 4 │
├───────┼───────┼───────┤
│0 1 4 │2 5 │3 │
├───────┼───────┼───────┤
│0 1 │2 4 5 │3 │
├───────┼───────┼───────┤
│0 1 │2 5 │3 4 │
├───────┼───────┼───────┤
│0 1 4 │2 │3 5 │
├───────┼───────┼───────┤
│0 1 │2 4 │3 5 │
├───────┼───────┼───────┤
│0 1 │2 │3 4 5 │
├───────┼───────┼───────┤
│0 2 3 5│1 │4 │
├───────┼───────┼───────┤
│0 3 5 │1 2 │4 │
├───────┼───────┼───────┤
│0 2 5 │1 3 │4 │
├───────┼───────┼───────┤
│0 5 │1 2 3 │4 │
├───────┼───────┼───────┤
│0 2 3 │1 5 │4 │
├───────┼───────┼───────┤
│0 3 │1 2 5 │4 │
├───────┼───────┼───────┤
│0 2 │1 3 5 │4 │
├───────┼───────┼───────┤
│0 │1 2 3 5│4 │
├───────┼───────┼───────┤
│0 2 3 │1 │4 5 │
├───────┼───────┼───────┤
│0 3 │1 2 │4 5 │
├───────┼───────┼───────┤
│0 2 │1 3 │4 5 │
├───────┼───────┼───────┤
│0 │1 2 3 │4 5 │
├───────┼───────┼───────┤
│0 1 3 5│2 │4 │
├───────┼───────┼───────┤
│0 1 5 │2 3 │4 │
├───────┼───────┼───────┤
│0 1 3 │2 5 │4 │
├───────┼───────┼───────┤
│0 1 │2 3 5 │4 │
├───────┼───────┼───────┤
│0 1 3 │2 │4 5 │
├───────┼───────┼───────┤
│0 1 │2 3 │4 5 │
├───────┼───────┼───────┤
│0 1 2 5│3 │4 │
├───────┼───────┼───────┤
│0 1 2 │3 5 │4 │
├───────┼───────┼───────┤
│0 1 2 │3 │4 5 │
├───────┼───────┼───────┤
│0 2 3 4│1 │5 │
├───────┼───────┼───────┤
│0 3 4 │1 2 │5 │
├───────┼───────┼───────┤
│0 2 4 │1 3 │5 │
├───────┼───────┼───────┤
│0 4 │1 2 3 │5 │
├───────┼───────┼───────┤
│0 2 3 │1 4 │5 │
├───────┼───────┼───────┤
│0 3 │1 2 4 │5 │
├───────┼───────┼───────┤
│0 2 │1 3 4 │5 │
├───────┼───────┼───────┤
│0 │1 2 3 4│5 │
├───────┼───────┼───────┤
│0 1 3 4│2 │5 │
├───────┼───────┼───────┤
│0 1 4 │2 3 │5 │
├───────┼───────┼───────┤
│0 1 3 │2 4 │5 │
├───────┼───────┼───────┤
│0 1 │2 3 4 │5 │
├───────┼───────┼───────┤
│0 1 2 4│3 │5 │
├───────┼───────┼───────┤
│0 1 2 │3 4 │5 │
├───────┼───────┼───────┤
│0 1 2 3│4 │5 │
└───────┴───────┴───────┘
[r2=: >r (*/)@:{&.>"1 0 < v
12 1 2
6 2 2
6 1 4
6 2 2
3 4 2
3 2 4
6 1 4
3 2 4
3 1 8
4 3 2
2 6 2
2 3 4
2 6 2
1 12 2
1 6 4
2 3 4
1 6 4
1 3 8
4 1 6
2 2 6
2 1 12
2 2 6
1 4 6
1 2 12
2 1 12
1 2 12
1 1 24
12 1 2
6 2 2
6 2 2
3 4 2
6 1 4
3 2 4
4 3 2
2 6 2
2 6 2
1 12 2
2 3 4
1 6 4
4 1 6
2 2 6
2 2 6
1 4 6
2 1 12
1 2 12
6 2 2
3 4 2
3 2 4
2 6 2
1 12 2
1 6 4
2 2 6
1 4 6
1 2 12
12 1 2
6 2 2
6 2 2
3 4 2
4 3 2
2 6 2
2 6 2
1 12 2
4 1 6
2 2 6
2 2 6
1 4 6
6 2 2
3 4 2
2 6 2
1 12 2
2 2 6
1 4 6
6 2 2
2 6 2
2 2 6
8 1 3
4 2 3
4 2 3
2 4 3
4 2 3
2 4 3
2 4 3
1 8 3
4 2 3
2 4 3
2 4 3
1 8 3
4 2 3
2 4 3
4 2 3
[r3=:/:~"1 r2
1 2 12
2 2 6
1 4 6
2 2 6
2 3 4
2 3 4
1 4 6
2 3 4
1 3 8
2 3 4
2 2 6
2 3 4
2 2 6
1 2 12
1 4 6
2 3 4
1 4 6
1 3 8
1 4 6
2 2 6
1 2 12
2 2 6
1 4 6
1 2 12
1 2 12
1 2 12
1 1 24
1 2 12
2 2 6
2 2 6
2 3 4
1 4 6
2 3 4
2 3 4
2 2 6
2 2 6
1 2 12
2 3 4
1 4 6
1 4 6
2 2 6
2 2 6
1 4 6
1 2 12
1 2 12
2 2 6
2 3 4
2 3 4
2 2 6
1 2 12
1 4 6
2 2 6
1 4 6
1 2 12
1 2 12
2 2 6
2 2 6
2 3 4
2 3 4
2 2 6
2 2 6
1 2 12
1 4 6
2 2 6
2 2 6
1 4 6
2 2 6
2 3 4
2 2 6
1 2 12
2 2 6
1 4 6
2 2 6
2 2 6
2 2 6
1 3 8
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
2 3 4
1 3 8
2 3 4
2 3 4
2 3 4
1 3 8
2 3 4
2 3 4
2 3 4
[r4=: ~.r3
1 2 12
2 2 6
1 4 6
2 3 4
1 3 8
1 1 24
*./24 =*/"1 r4
1
NB. All permutations
(!3)*#r5
312
---------------------------------------------------------------------
- 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
----------------------------------------------------------------------
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
