[Tim]
[MRAB, posts a beautiful solution]
I don't really have a use for this, but it was a lovely programming puzzle, so I'll include an elaborate elaboration of MRAB's algorithm below. And that's the end of my interest in this;-)
[Ron Adam]
A what the heck... :-)
This is what I came up with which works like MRAB's by removing the first element and using recursion on the rest. (It's how you do it in lisp or scheme.)
It's solving a different problem, though. In your "Return all unique combinations of elements in seq", by "unique" you really mean "by position", not " by value". For example:
for p in unique_sets('aab'): ... print(p) ['a'] ['a'] ['b'] ['b', 'a'] ['a', 'a'] ['b', 'a'] ['b', 'a', 'a']
See? ['a'] is produced twice, and so is ['b', 'a']. The whole point of the algorithms in the thread this spawned from was to avoid generating *value*-duplicates to begin with. Filtering them out later is too inefficient.
for p in unique_sets('aaaaaaaaaa'): ... print(p) ['a'] ['a'] ['a'] ['a'] ['a'] ['a'] ['a'] ['a'] ['a'] ['a'] ['a', 'a'] ['a', 'a'] ['a', 'a'] ['a', 'a', 'a'] ['a', 'a'] ['a', 'a'] ['a', 'a'] ['a', 'a', 'a'] ... on and on and on ....
Only one comment on the code:
def unique_sets(seq): """Return all unique combinations of elements in seq.""" if len(seq) == 0: return [] first, rest = seq[0], seq[1:]
Python's newer unpacking syntax makes that one prettier: first, *rest = seq Much higher-level than crusty old Lisp or Scheme ;-)
....