Date: 09/03/06 (Algorithms)    Keywords: no keywords

First post of mine in this group. I am using Python here, but I understand some other procedural languages too.

The permutations of the elements of the array [1, 2, 3] are:
[[1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2], [2, 3, 1], [3, 2, 1]]


To find the unique permutations I use this brute force way:

def uniqPermutations(items):
__cache = set()
__for el in xpermutations(items):
____tel = tuple(el)
____if tel not in cache:
______cache.add(tel)
______yield el

(Note: yield turns this function in a state-based generator. cache is a set data structure. A tuple is like a list, but it can be hashed and put into a Python set. xpermutations is another generator function that gives all the permutations.)


uniqPermutations([1,2,1]) returns:
[1, 2, 1] [2, 1, 1] [1, 1, 2]

I'd like an algorithm to find such unique permutations that doesn't require all that memory (And I'll need a similar algorithm to find the unique combinations too).

Bye and thank you.

Source: http://community.livejournal.com/algorithms/83323.html