[Jprogramming] Partitions
Erling Hellenäs
erling at erlinghellenas.se
Tue Nov 7 10:50:30 UTC 2017
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:programming-bounces at forums.jsoftware.com]
>> On Behalf Of Erling Hellenäs
>> Sent: Sunday, November 5, 2017 11:28 AM
>> To: programming at jsoftware.com
>> 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
More information about the Programming
mailing list