I have an array of objects and I need to generate all permutations.
e.g. for [1,2,3] I get:
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
This problem is actually easy to solve and in fact there is a purely
iterative solution.
However in my case I also need to solve a variant of this problem.
In this variant the array has 2n elements grouped into n groups of two
elements
where each 2 element pair are equal.
For example for array [1,1,2,2] I get:
[1,1,2,2]
[1,2,1,2]
[1,2,2,1]
[2,1,1,2]
[2,1,2,1]
[2,2,1,1]
Note that in the first case I get n! permutations whereas in the
second case
I get (2n)! / 2^n permutations. I want to generate the permutations
efficiently.
I particular it is unacceptable to generate the (2n)! combinations and
then
remove the duplicates. I have come up only with complicated ways of
doing this
but I am hoping someone can post or reference a simpler solution.
A solution that generalizes in various ways would be nice but not
important to my
particular problem.
I will be implementing the final solution in Smalltalk (Squeak) and
eventually in other
languages as part of an implentation of the spine tree decomposition
data structure.
It will be released (in Squeak at least) under the MIT license.
It is also so easy, but maybe requires more lines of code
you only need count number of used number for each 1..n
and then...(repeat recursive approach)
ONE LINE SOLUTION IN C++
ok use next permutation from STL, read how it works for other language
and initialize array 11223344, and do while next_permutaion()...
it actualy gives you always next lexicographical permutation of sequence
> I have an array of objects and I need to generate all permutations.
> e.g. for [1,2,3] I get:
> [1,2,3]
> [1,3,2]
> [2,1,3]
> [2,3,1]
> [3,1,2]
> [3,2,1]
> This problem is actually easy to solve and in fact there is a purely
> iterative solution.
> However in my case I also need to solve a variant of this problem.
> In this variant the array has 2n elements grouped into n groups of two
> elements
> where each 2 element pair are equal.
> For example for array [1,1,2,2] I get:
> [1,1,2,2]
> [1,2,1,2]
> [1,2,2,1]
> [2,1,1,2]
> [2,1,2,1]
> [2,2,1,1]
> Note that in the first case I get n! permutations whereas in the
> second case
> I get (2n)! / 2^n permutations. I want to generate the permutations
> efficiently.
> I particular it is unacceptable to generate the (2n)! combinations and
> then
> remove the duplicates. I have come up only with complicated ways of
> doing this
> but I am hoping someone can post or reference a simpler solution.
> A solution that generalizes in various ways would be nice but not
> important to my
> particular problem.
> I will be implementing the final solution in Smalltalk (Squeak) and
> eventually in other
> languages as part of an implentation of the spine tree decomposition
> data structure.
> It will be released (in Squeak at least) under the MIT license.
> It is also so easy, but maybe requires more lines of code
> you only need count number of used number for each 1..n
> and then...(repeat recursive approach)
> ONE LINE SOLUTION IN C++
> ok use next permutation from STL, read how it works for other language
> and initialize array 11223344, and do while next_permutaion()...
> it actualy gives you always next lexicographical permutation of sequence
> you can also view source code of it in libraries
>> I have an array of objects and I need to generate all permutations.
>> e.g. for [1,2,3] I get:
>> [1,2,3]
>> [1,3,2]
>> [2,1,3]
>> [2,3,1]
>> [3,1,2]
>> [3,2,1]
>> This problem is actually easy to solve and in fact there is a purely
>> iterative solution.
>> However in my case I also need to solve a variant of this problem.
>> In this variant the array has 2n elements grouped into n groups of two
>> elements
>> where each 2 element pair are equal.
>> For example for array [1,1,2,2] I get:
>> [1,1,2,2]
>> [1,2,1,2]
>> [1,2,2,1]
>> [2,1,1,2]
>> [2,1,2,1]
>> [2,2,1,1]
>> Note that in the first case I get n! permutations whereas in the
>> second case
>> I get (2n)! / 2^n permutations. I want to generate the permutations
>> efficiently.
>> I particular it is unacceptable to generate the (2n)! combinations and
>> then
>> remove the duplicates. I have come up only with complicated ways of
>> doing this
>> but I am hoping someone can post or reference a simpler solution.
>> A solution that generalizes in various ways would be nice but not
>> important to my
>> particular problem.
>> I will be implementing the final solution in Smalltalk (Squeak) and
>> eventually in other
>> languages as part of an implentation of the spine tree decomposition
>> data structure.
>> It will be released (in Squeak at least) under the MIT license.
> Yeah c++ STL nextpermutation api will do it .. good solution Miroslav!
> On Tue, Jun 23, 2009 at 10:25 PM, Miroslav Balaz <gpsla...@googlemail.com>wrote:
> > It is also so easy, but maybe requires more lines of code
> > you only need count number of used number for each 1..n
> > and then...(repeat recursive approach)
> > ONE LINE SOLUTION IN C++
> > ok use next permutation from STL, read how it works for other language
> > and initialize array 11223344, and do while next_permutaion()...
> > it actualy gives you always next lexicographical permutation of sequence
> > you can also view source code of it in libraries
> >> I have an array of objects and I need to generate all permutations.
> >> e.g. for [1,2,3] I get:
> >> [1,2,3]
> >> [1,3,2]
> >> [2,1,3]
> >> [2,3,1]
> >> [3,1,2]
> >> [3,2,1]
> >> This problem is actually easy to solve and in fact there is a purely
> >> iterative solution.
> >> However in my case I also need to solve a variant of this problem.
> >> In this variant the array has 2n elements grouped into n groups of two
> >> elements
> >> where each 2 element pair are equal.
> >> For example for array [1,1,2,2] I get:
> >> [1,1,2,2]
> >> [1,2,1,2]
> >> [1,2,2,1]
> >> [2,1,1,2]
> >> [2,1,2,1]
> >> [2,2,1,1]
> >> Note that in the first case I get n! permutations whereas in the
> >> second case
> >> I get (2n)! / 2^n permutations. I want to generate the permutations
> >> efficiently.
> >> I particular it is unacceptable to generate the (2n)! combinations and
> >> then
> >> remove the duplicates. I have come up only with complicated ways of
> >> doing this
> >> but I am hoping someone can post or reference a simpler solution.
> >> A solution that generalizes in various ways would be nice but not
> >> important to my
> >> particular problem.
> >> I will be implementing the final solution in Smalltalk (Squeak) and
> >> eventually in other
> >> languages as part of an implentation of the spine tree decomposition
> >> data structure.
> >> It will be released (in Squeak at least) under the MIT license.
|
