[Python-ideas] Fwd: Extremely weird itertools.permutations

[MRAB]

On 12/10/2013 02:55, MRAB wrote:
> On 12/10/2013 00:49, Nick Coghlan wrote:
>>
>> On 12 Oct 2013 08:45, "David Mertz" <mertz at gnosis.cx
>> <mailto:mertz at gnosis.cx>> wrote:
>>  >
>>  >
>>  > I realize after reading
>> http://stackoverflow.com/questions/6284396/permutations-with-unique-values
>> that my version was ALMOST right:
>>  >
>>  > def nonredundant_permutations(seq, r=None):
>>  >     last = ()
>>  >     for perm in permutations(sorted(seq), r):
>>  >         if perm > last:
>>  >             yield perm
>>  >             last = perm
>>  >
>>  > I can't look only for inequality, but must use the actual comparison.
>>  >
>>  > >>> ["".join(x) for x in nonredundant_permutations('aaabb',3)]
>>  > ['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba']
>>  > >>> list(nonredundant_permutations([F(3,1), D(3.0), 3.0]))
>>  > [(Fraction(3, 1), Decimal('3'), 3.0)]
>>  >
>>  > Of course, this approach DOES rely on the order in which
>> itertools.permutations() returns values.  However, it's a bit more
>> compact than MRAB's version.
>>
>> As there is no requirement that entries in a sequence handled by
>> itertools.permutations be sortable, so the original question of why this
>> isn't done by default has been answered (the general solution risks
>> consuming too much memory, while the memory efficient solution
>> constrains the domain to only sortable sequences).
>>
> OK, here's a new implementation:
>
[snip]
I've just realised that I don't need to sort them at all.

Here's a new improved implementation:

def unique_permutations(iterable, count=None):
     def perm(items, count):
         if count:
             seen = set()

             for i, item in enumerate(items):
                 if item not in seen:
                     for p in perm(items[ : i] + items[i + 1 : ], count 
- 1):
                         yield [item] + p

                     seen.add(item)
         else:
             yield []

     items = list(iterable)

     if count is None:
         count = len(items)

     yield from perm(items, count)