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