Re: [julia-users] Re: Better alternative to find all permutations?

[Ratan Sur]

Any consensus on this?

On Monday, November 23, 2015 at 8:52:54 PM UTC+5:30, Stefan Karpinski wrote:
>
> 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.
>
> On Mon, Nov 23, 2015 at 8:03 AM, Tamas Papp  > wrote:
>
>> 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  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  
>> 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 > >
>> >> wrote:
>> >> >
>> >> >> 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.
>> >> >>
>> >> >> On Saturday, 21 November 2015 04:24:51 UTC+10, Jiahao Chen wrote:
>> >> >>>
>> >> >>> 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
>> >> >>>
>> >> >>
>> >>
>> >>
>>
>
>

Re: [julia-users] Re: Better alternative to find all permutations?

[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)]

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  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  
> wrote: 
> > 
> >> 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. 
> >> 
> >> On Saturday, 21 November 2015 04:24:51 UTC+10, Jiahao Chen wrote: 
> >>> 
> >>> 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
>  
> >>> 
> >> 
>
>

Re: [julia-users] Re: Better alternative to find all permutations?

[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  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  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 
>> wrote:
>> >
>> >> 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.
>> >>
>> >> On Saturday, 21 November 2015 04:24:51 UTC+10, Jiahao Chen wrote:
>> >>>
>> >>> 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
>> >>>
>> >>
>>
>>

Re: [julia-users] Re: Better alternative to find all permutations?

[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.

On Monday, 23 November 2015 04:50:45 UTC+10, Ratan Sur 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  
> wrote:
>
>> 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.
>>
>> On Saturday, 21 November 2015 04:24:51 UTC+10, Jiahao Chen wrote:
>>>
>>> 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
>>>
>>

Re: [julia-users] Re: Better alternative to find all permutations?

[Tamas Papp]

On Mon, Nov 23 2015, Glen O  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

Re: [julia-users] Re: Better alternative to find all permutations?

[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.

On Mon, Nov 23, 2015 at 8:03 AM, Tamas Papp  wrote:

> 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  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 
> 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  >
> >> wrote:
> >> >
> >> >> 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.
> >> >>
> >> >> On Saturday, 21 November 2015 04:24:51 UTC+10, Jiahao Chen wrote:
> >> >>>
> >> >>> 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
> >> >>>
> >> >>
> >>
> >>
>

Re: [julia-users] Re: Better alternative to find all permutations?

[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.

Re: [julia-users] Re: Better alternative to find all permutations?

[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.

On Sun, Nov 22, 2015 at 2:16 AM Glen O  wrote:

> 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.
>
> On Saturday, 21 November 2015 04:24:51 UTC+10, Jiahao Chen wrote:
>>
>> 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
>>
>

Re: [julia-users] Re: Better alternative to find all 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

On Sun, Nov 22 2015, Ratan Sur  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  wrote:
>
>> 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.
>>
>> On Saturday, 21 November 2015 04:24:51 UTC+10, Jiahao Chen wrote:
>>>
>>> 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
>>>
>>

Re: [julia-users] Re: Better alternative to find all permutations?

[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.

On Saturday, 21 November 2015 04:24:51 UTC+10, Jiahao Chen wrote:
>
> 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
>

Re: [julia-users] Re: Better alternative to find all permutations?

[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

Re: [julia-users] Re: Better alternative to find all permutations?

[Stefan Karpinski]

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

On Fri, Nov 20, 2015 at 1:24 PM, Jiahao Chen  wrote:

> 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
>

Re: [julia-users] Re: Better alternative to find all 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"*".





On Fri, Nov 20, 2015 at 1:32 PM, Stefan Karpinski 
wrote:

> What about the argument that you can always permute indices if you want
> all distinct permutations?
>
> On Fri, Nov 20, 2015 at 1:24 PM, Jiahao Chen  wrote:
>
>> 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
>>
>
>

Re: [julia-users] Re: Better alternative to find all permutations?

[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.

On Thu, Nov 19, 2015 at 4:06 PM, David P. Sanders 
wrote:

>
>
> El jueves, 19 de noviembre de 2015, 14:45:41 (UTC-6), Ratan Sur escribió:
>>
>> 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]
>>
>>
> It turns out that the following works:
>
> unique(permutations([1, 0, 0, 0, 1]))
>
>
>

[julia-users] Re: Better alternative to find all permutations?

[rafzalan]

sorry for typo error in *permutations*.

[julia-users] Re: Better alternative to find all permutations?

[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)
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

Re: [julia-users] Re: Better alternative to find all permutations?

[Ratan Sur]

I sense pull requests :P

On Thu, Nov 19, 2015, 18:57 Dan  wrote:

> 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 ;)
>

[julia-users] Re: Better alternative to find all permutations?

[David P. Sanders]

El jueves, 19 de noviembre de 2015, 14:45:41 (UTC-6), Ratan Sur escribió:
>
> 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]
>
>
It turns out that the following works:

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

 

Re: [julia-users] Re: Better alternative to find all permutations?

[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"

On Thursday, November 19, 2015 at 4:12:35 PM UTC-5, Stefan Karpinski wrote:
>
> 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.
>
> On Thu, Nov 19, 2015 at 4:06 PM, David P. Sanders  > wrote:
>
>>
>>
>> El jueves, 19 de noviembre de 2015, 14:45:41 (UTC-6), Ratan Sur escribió:
>>>
>>> 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]
>>>
>>>
>> It turns out that the following works:
>>
>> unique(permutations([1, 0, 0, 0, 1]))
>>
>>  
>>
>
>

Re: [julia-users] Re: Better alternative to find all permutations?

[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.

On Thu, Nov 19, 2015 at 4:16 PM, Ratan Sur  wrote:

> 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"
>
> On Thursday, November 19, 2015 at 4:12:35 PM UTC-5, Stefan Karpinski wrote:
>>
>> 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.
>>
>> On Thu, Nov 19, 2015 at 4:06 PM, David P. Sanders 
>> wrote:
>>
>>>
>>>
>>> El jueves, 19 de noviembre de 2015, 14:45:41 (UTC-6), Ratan Sur escribió:

 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]


>>> It turns out that the following works:
>>>
>>> unique(permutations([1, 0, 0, 0, 1]))
>>>
>>>
>>>
>>
>>

[julia-users] Re: Better alternative to find all permutations?

[rafzalan]

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
>

Re: [julia-users] Re: Better alternative to find all permutations?

[Jeffrey Sarnoff]

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

On Thursday, November 19, 2015 at 4:30:54 PM UTC-5, Stefan Karpinski wrote:
>
> 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.
>
> On Thu, Nov 19, 2015 at 4:16 PM, Ratan Sur  > wrote:
>
>> 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"
>>
>> On Thursday, November 19, 2015 at 4:12:35 PM UTC-5, Stefan Karpinski 
>> wrote:
>>>
>>> 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.
>>>
>>> On Thu, Nov 19, 2015 at 4:06 PM, David P. Sanders  
>>> wrote:
>>>


 El jueves, 19 de noviembre de 2015, 14:45:41 (UTC-6), Ratan Sur 
 escribió:
>
> 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]
>
>
 It turns out that the following works:

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

  

>>>
>>>
>

[julia-users] Re: Better alternative to find all permutations?

[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.