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