[julia-users] Enumerating permutations

[Christopher Fisher]

I was wondering if there is a function for enumerating all of the
permutations of size m from n elements, with repetitions allowed. For
example, 3 permutations of [1 0] would be [ 1 1 1;1 1 0;1 0 1;0 1 1;1 0 0;
0 1 0;0 0 1; 0 0 0]. (Analogous
to http://www.mathworks.com/matlabcentral/fileexchange/11462-npermutek/content/npermutek.m)

Along similar lines, I was wondering if there is a function for
permutations without repetitions, such as 2 elements from [1 2 3] is [1 2;1
3;2 3;2 1;3 1;3 2]. I see that there is a permutations function but it only
enumerates permutations of the same size as the original set.

Thank you

[Tamas Papp]

Post by Christopher Fisher
I was wondering if there is a function for enumerating all of
the permutations of size m from n elements, with repetitions
allowed. For example, 3 permutations of [1 0] would be [ 1 1
1;1 1 0;1 0 1;0 1 1;1 0 0; 0 1 0;0 0 1; 0 0 0]. (Analogous to
http://www.mathworks.com/matlabcentral/fileexchange/11462-npermutek/content/npermutek.m)

Perhaps something like (not tested extensively, check for bugs)

@doc "All length `n` sequences of `1:v` in a matrix, with
repetitions."-> function perm_matrix{T}(v::T, n)
m = v^n a = zeros(T, m, n) for i = 1:m
k = i-1 j = n while ((k > 0) && (j > 0))
(d,r) = divrem(k,v) a[i,j] = r k = d j -= 1
end
end a
end perm_matrix(3, 2)

Post by Christopher Fisher
Along similar lines, I was wondering if there is a function for
permutations without repetitions, such as 2 elements from [1 2
3] is [1 2;1 3;2 3;2 1;3 1;3 2]. I see that there is a
permutations function but it only enumerates permutations of
the same size as the original set.

Did you have a look at the function Base.combinations? Unless I
misunderstand your question, it does what you are asking for.

Best,

Tamas

[Christopher Fisher]

Thank you Tamas. I added return a and restructured the code (I think some
formatting was lost when pasting). Based on the examples I tested, it
appears to work. Can you recommend an efficient method of inputing an array
of numbers. For example:

a = [10,12]

p = perm_matrix(a,2)

p = [10 10; 10 12; 12 10; 12 12]

I could probably hack something together that maps elements of a to the
elements of p (0 through n-1), but you might have a more efficient and
elegant solution.


Regarding the second question, the combinations function (I believe this is
what you were referring to) would treat (1,2) and (2,1) as
indistinguishable. For example, the code below yields only three unordered
pairs rather than six ordered pairs

In [9]:

collect(combinations([1;2;3],2))

Out[9]:

3-element Array{Array{Int64,1},1}:
[1,2]
[1,3]
[2,3]


Thanks again

Post by Christopher Fisher

Post by Christopher Fisher
I was wondering if there is a function for enumerating all of
the permutations of size m from n elements, with repetitions
allowed. For example, 3 permutations of [1 0] would be [ 1 1
1;1 1 0;1 0 1;0 1 1;1 0 0; 0 1 0;0 0 1; 0 0 0]. (Analogous to

http://www.mathworks.com/matlabcentral/fileexchange/11462-npermutek/content/npermutek.m)
Perhaps something like (not tested extensively, check for bugs)
@doc "All length `n` sequences of `1:v` in a matrix, with
repetitions."-> function perm_matrix{T}(v::T, n)
m = v^n a = zeros(T, m, n) for i = 1:m
k = i-1 j = n while ((k > 0) && (j > 0))
(d,r) = divrem(k,v) a[i,j] = r k = d j -= 1
end
end a
end perm_matrix(3, 2)

Post by Christopher Fisher
Along similar lines, I was wondering if there is a function for
permutations without repetitions, such as 2 elements from [1 2
3] is [1 2;1 3;2 3;2 1;3 1;3 2]. I see that there is a
permutations function but it only enumerates permutations of
the same size as the original set.

Did you have a look at the function Base.combinations? Unless I
misunderstand your question, it does what you are asking for.
Best,
Tamas

[Tamas Papp]

Post by Christopher Fisher
Thank you Tamas. I added return a and restructured the code (I
think some formatting was lost when pasting). Based on the
examples I tested, it appears to work. Can you recommend an
a = [10,12]
p = perm_matrix(a,2)
p = [10 10; 10 12; 12 10; 12 12]
I could probably hack something together that maps elements of a
to the elements of p (0 through n-1), but you might have a more
efficient and elegant solution.

A trivial modification takes care of that, see
https://gist.github.com/tpapp/43131b48f1afd97f1018

Post by Christopher Fisher
Regarding the second question, the combinations function (I
believe this is what you were referring to) would treat (1,2)
and (2,1) as indistinguishable. For example, the code below
yields only three unordered pairs rather than six ordered pairs

Just use permutations --- see example in the gist above.

Best,

Tamas

[Christopher Fisher]

Excellent. a[i,j] = v[r+1] was essentially the mapping I had in mind.
Thanks for sharing the code!

Post by Tamas Papp

Post by Christopher Fisher
Thank you Tamas. I added return a and restructured the code (I
think some formatting was lost when pasting). Based on the
examples I tested, it appears to work. Can you recommend an
a = [10,12]
p = perm_matrix(a,2)
p = [10 10; 10 12; 12 10; 12 12]
I could probably hack something together that maps elements of a
to the elements of p (0 through n-1), but you might have a more
efficient and elegant solution.

A trivial modification takes care of that, see
https://gist.github.com/tpapp/43131b48f1afd97f1018

Post by Christopher Fisher
Regarding the second question, the combinations function (I
believe this is what you were referring to) would treat (1,2)
and (2,1) as indistinguishable. For example, the code below
yields only three unordered pairs rather than six ordered pairs

Just use permutations --- see example in the gist above.
Best,
Tamas