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 > > > 2009/6/23 Ralph Boland <rpbol...@gmail.com> > > >> 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. >> >> Thanks for any help provided. >> >> Ralph Boland >> >> > > > > -- Ciao, Ajinkya --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
