Please see http://geeksforgeeks.org/?p=767 for well explained C implementation of the same.
On Jun 23, 10:01 am, Ajinkya Kale <kaleajin...@gmail.com> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
