Better alternative to find all permutations?

[Ratan Sur]

I want to get all the unique permutations of an array of a certain length and this is the only way I currently know how to do it in one line. Is there a builtin function for this?

julia> unique(collect(permutations([1;0;0;0;1])))

10-element Array{Array{Int64,1},1}:

 [1,0,0,0,1]

 [1,0,0,1,0]

 [1,0,1,0,0]

 [1,1,0,0,0]

 [0,1,0,0,1]

 [0,1,0,1,0]

 [0,1,1,0,0]

 [0,0,1,0,1]

 [0,0,1,1,0]

 [0,0,0,1,1]

[Eric Forgy]

Hi Ratan,

I don't know of a builtin function, but it looks like your code will first construct an array with all permutations and then reduce that to just the unique ones. I haven't used it yet, so hope I don't send you in the wrong direction, but you might have a look at Lazy.jl. That might help you avoid the initial step of constructing the full array.

[David P. Sanders]

It turns out that the following works:

unique(permutations([1, 0, 0, 0, 1]))

 

[Stefan Karpinski]

That's definitely more memory efficient, but not much more computationally efficient. There's probably a much cleverer way to compute the unique permutations of a set of values that contain repetitions. It's arguable that this is what permutations ought to do in the first place.

[Ratan Sur]

I saw a comment in combinatorics.jl that this stuff is being moved over there so I'll check out if that's the same implementation. I think my use of the function is more likely what people want when thinking: "oh, I want all the permutations of this array"

[Stefan Karpinski]

It is the same code. However, I do think that there's a strong case to be made that when the elements of an array are non-unique, you want the distinguishable permutations of it, not all of the permutations.

[Jeffrey Sarnoff]

I agree, permutations() should give the distinguishable permutations; allpermutations() should give each and every one.

[rafz...@gmail.com]

Hi, I already implemented lexicographic premutations generation algorithm based on a Donald Knuth work.

#lexicographic premutations generation, By Donald Knuth  
function lpremutations{T}(a::T)
  b=Vector{T}()
  sort!(a)
  n=length(a)
  while(true)
    push!(b,copy(a))    
    j=n-1
    while(a[j]>=a[j+1])
      j-=1
      j==0 && return(b)
    end
    l=n
    while(a[j]>=a[l])
      l-=1
    end
    tmp=a[l]
    a[l]=a[j]
    a[j]=tmp
    k=j+1
    l=n
    while(k<l)
      tmp=a[k]
      a[k]=a[l]
      a[l]=tmp
      k+=1
      l-=1
    end
  end
end

[Dan]

How about this:

using StatsBase
using Iterators

function uniquepermutations(base)
zpos = Vector{Vector{Vector{Int}}}()
zval = Vector{Int}()
left = length(base)
for (v,c) in countmap(base)
push!(zpos,collect(subsets(collect(1:left),c)))
push!(zval,v)
left -= c
end
res = Vector{Vector{Int}}()
for a in product(zpos...)
slots = collect(1:length(base))
perm = zeros(length(base))
for (val,b) in zip(zval,a)
perm[slots[b]] = val
slots[b] = 0
slots = filter(x->x>0,slots)
end
push!(res,perm)
end
res
end

Familiarity with `countmap`,`subsets`,`product`,`zip` from StatsBase and Iterators helps. The logic is straight-forward.

[Dan]

Well, the previous listing worked only for Int vectors. Following is a more properly typed version.
Various optimizations are possible: @inbounds, reducing allocations, etc.

function uniquepermutations(base)
zpos = Vector{Vector{Vector{Int}}}()

zval = Vector{eltype(base)}()

left = length(base)
for (v,c) in countmap(base)
push!(zpos,collect(subsets(collect(1:left),c)))
push!(zval,v)
left -= c
end

res = Vector{Vector{eltype(base)}}()

for a in product(zpos...)
slots = collect(1:length(base))

perm = similar(base)

[rafz...@gmail.com]

sorry for typo error in permutations.

[Dan]

Knuth's lexicographic permutations version is best (in terms of speed, memory. perhaps less readable).
The function name in the code snippet even has a little permutation by itself ;)

[Ratan Sur]

I sense pull requests :P

[Jiahao Chen]

The current behavior of permutations is correct and should not be changed. Combinatorially, arrays are multisets, not sets, since they allow for duplicate entries, so it is correct to produce what look like identical permutations. The redundancy is important for operations that can be expressed as sums over all permutations.

Combinatorics.jl currently provides multiset_permutations for generating only distinct permutations:

https://github.com/JuliaLang/Combinatorics.jl/blob/3c08c9af9ebeaa54589e939c0cf2e652ef4ca6a0/test/permutations.jl#L24-L25

[Stefan Karpinski]

What about the argument that you can always permute indices if you want all distinct permutations?

[Jeffrey Sarnoff]

Arrays are indexed sequences of indexable sequences of arrays .. to ground.

An array may exist whereof two or more distinct indices find content deemed indistinguishable were it devoid of the indexicalic contextualization that finds.

And one may count all the stars were the canopy devoid of of that that finds.

One may drop, forget, whatever may be unique of Array or of multiset or of cow.

Multisets are a sort of set, one that internalizes some setal structure as cubbies,

which is not at all a set of sets.  And a common sets are a sort of forgetful multiset, one that  forgets mutiplicity.

Together, the above is a fruitful basis on which to construct computation;

call it Sheaf Theory.

"permute and provide all possible indistinguishables," not "permute is provide"".

  

[Glen O]

While it is true that an interpretation of arrays is multisets, that's not the only reasonable interpretation. And while the strict interpretation of "permutations" suggests it should include duplicates, you have to consider what the user would most likely expect it to do. Most would think that a list of the permutations would include unique permutations only.

So perhaps both functionalities should be available in the same function with a keyword argument. At the very least, the description of the function should directly inform the user that it's going to give duplicate permutations if the array contains repeat elements.

[Ratan Sur]

I think julia more than other languages has a tendency to stick with mathematical consistency over some user preferences, which is good. For that reason, I would be in favor of permutations remaining as is but having multiset_permutations renamed to something more intuitive, like uniqueperms, or unique_permutations.

[Tamas Papp]

Also, "unique" permutations require a notion of equality, and which is
hard to define in general (classic essay is [1], about Common Lisp,
but applies to Julia mutatis mutandis). At least Julia has bits types
for numbers, which makes life a bit easier.

Whether one picks is, isequal, or == for comparison, it easy to come up
with cases which go against user expectations (at least for some
users). For example, given

type Foo end
type Bar x end

what should be the unique permutations of

[0.0,-0.0,NaN,NaN,Foo(),Foo(),Bar(NaN),Bar(NaN)]

?

Best,

Tamas

[1] http://www.nhplace.com/kent/PS/EQUAL.html

[Dan]

If we are already at this, it would be cool to have versions with Gray ordering.
Something like:

for (i1,i2) in permutations(vector,indices=true,Gray=true)
theperm[[i1,i2]] = theperm[[i2,i1]]
@show theperm
end

would go over all permutations.
The syntax would be different and this is not a Gray order use-case.
But Gray ordering is useful and compact.

[Glen O]

Logically, the same definition being used by "unique" would be applied, unless specified otherwise (which should also be available for unique - it's silly that you can't specify the level of inequality necessary for uniqueness).

Incidentally, in the example you gave, unique gives [0.0,-0.0,NaN,Foo(),Bar(NaN),Bar(NaN)]

[Glen O]

Mathematical consistency is nice, to be sure, but it's important that the user gets the behaviour that they would expect. There is nothing in the name "Permutations", nor in the description given by help, that makes it clear to the user that the permutations include identical permutations. The only people who would expect the current behaviour are combinatorialists and maybe computer scientists. If I asked you to write out the permutations of the string "test", you wouldn't include the word "test" twice on the list (unless you're in one of the aforementioned categories, that is).

multiset_permutations is certainly too obscure as a name, and overly long to boot (the latter issue applies to unique_permutations, too). uniqueperms is a bit better (but might cause a little confusion with the "perm" commands for permissions).

I personally think that incorporating an option into the existing function is a better approach - permutations(A,unique=true) to only include unique permutations. The default would be unique=false, which would cause the code to produce all permutations, including the duplicates. Then the help message can explain the option, and that also makes clear what the default behaviour will do.

[Tamas Papp]

On Mon, Nov 23 2015, Glen O <gjo...@gmail.com> wrote:

> Mathematical consistency is nice, to be sure, but it's important that the
> user gets the behaviour that they would expect. There is nothing in the
> name "Permutations", nor in the description given by help, that makes it
> clear to the user that the permutations include identical permutations. The
> only people who would expect the current behaviour are combinatorialists
> and maybe computer scientists. If I asked you to write out the permutations

I am neither a combinatorialist nor a computer scientist, and I expect
the current behavior, so perhaps your statement is not true. Different
users expect different things, and expectations can be (and are)
adjusted with experience. So it is hard to design for these things.

I think that these kind of discussions move very quickly from "I didn't
expect it" to "violates user expectations" without a lot of additional
data. I understand that Julia is a new language so people would like to
mold it to their own expectations, and surely there are a lot of things
that can be improved. Personally, I prefer mathematical consistency,
simplicity and composability to DWIM special cases.

Best,

Tamas

[Tamas Papp]

IMO permutations should maintain the following invariant: for any vector
v,

isequal(map(i -> getindex(v,i), collect(permutations(1:length(v)))),
collect(permutations(v)))

Bringing equality and uniqueness into the issue disposes of this
property, which is desirable in many applications.

Best,

Tamas

On Mon, Nov 23 2015, Glen O <gjo...@gmail.com> wrote:

> Logically, the same definition being used by "unique" would be applied,
> unless specified otherwise (which should also be available for unique -
> it's silly that you can't specify the level of inequality necessary for
> uniqueness).
>
> Incidentally, in the example you gave, unique gives
> [0.0,-0.0,NaN,Foo(),Bar(NaN),Bar(NaN)]
>
> On Monday, 23 November 2015 05:08:12 UTC+10, Tamas Papp wrote:
>>
>> Also, "unique" permutations require a notion of equality, and which is
>> hard to define in general (classic essay is [1], about Common Lisp,
>> but applies to Julia mutatis mutandis). At least Julia has bits types
>> for numbers, which makes life a bit easier.
>>
>> Whether one picks is, isequal, or == for comparison, it easy to come up
>> with cases which go against user expectations (at least for some
>> users). For example, given
>>
>> type Foo end
>> type Bar x end
>>
>> what should be the unique permutations of
>>
>> [0.0,-0.0,NaN,NaN,Foo(),Foo(),Bar(NaN),Bar(NaN)]
>>
>> ?
>>
>> Best,
>>
>> Tamas
>>
>> [1] http://www.nhplace.com/kent/PS/EQUAL.html
>>

>> On Sun, Nov 22 2015, Ratan Sur <ratan...@gmail.com <javascript:>> wrote:
>>
>> > I think julia more than other languages has a tendency to stick with
>> > mathematical consistency over some user preferences, which is good. For
>> > that reason, I would be in favor of permutations remaining as is but
>> having
>> > multiset_permutations renamed to something more intuitive, like
>> > uniqueperms, or unique_permutations.
>> >

>> > On Sun, Nov 22, 2015 at 2:16 AM Glen O <gjo...@gmail.com <javascript:>>

[Stefan Karpinski]

Any algorithm for producing unique permutations obviously needs to rely on some notion of element equality. That could be user-defined but default to something sane. I suspect that isequal or === would be good choices; == is not a good choice since NaN is not even == to itself.

[Ratan Sur]

Any consensus on this?