On 10/15/2013 07:25 PM, Tim Peters wrote:
[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:
Correct. And sometimes an items position is part of what makes it unique. Multiple roller combination locks and slot-machines, come to mind. I'm sure there are other things where the label or face value is only one aspect of it's identity.
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.
Well, we can filter them to begin-with instead of later. for p in unique_sets(list(set('aaaaaaaa'))): print(p) ['a'] And skip combination duplicates later as they are produced. for p in unique_sets('aaaaaaaa'): if cached(tuple(p)): continue 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'] ['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'] Not generating them to begin with requires some sort of known ordering or pattern in the data. The difference between checking them inside the algorithm as they are produced, and checking them externally as they are *yielded* is only the yield overhead if we are talking about python code in both places. In effect the inner loop control is yielded out with the value. That's a very nice thing about "yield from", and it still works that way in the recursive example. That makes things like this a lot more flexible.
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
LOL... yep. Thats why that part bugged me. I knew there was something I was missing. The other part that bothers me is the insistence list check. And not accepting sets directly.
Much higher-level than crusty old Lisp or Scheme ;-)
HAHA... yep, although they are both new to me and clojure seems to be doing well. A little digression... I've been thinking that pythons byte code could be a little higher level and still be efficient. So I wrote a little interpreter (in python) to test some ideas. * Use nested [sequences] in the bytecode rather than jumps. * Use tuples to contain the function followed by it's arguments.. (very easy to parse and evaluate this way). * Keep bytecodes and keywords to a minimal set. * Use as little punctuation symbols as possible. I didn't start learning lisp and scheme until after I got that much working. But it turned out (and I recently found out) it to be very close to a scheme interpreter or lisp interpreter. This example works, with some syntax alterations from the lisp version. And after adding in the needed standard lisp/scheme functions.. car, cdr, etc... (Looks much nicer with syntax highlighting.) def "power-set set" [ if (is-empty set) [return (list set)] let psets-without-car (power-set (cdr set)) let psets-with-car (mapcar (cons (lambda 'subset' [return (cons (car set) subset)]) psets-without-car)) return (join-lists psets-with-car psets-without-car) ] echo (power-set [[1 2] [3 4] [5 6]]) (power-set [[1 2] [3 4] [5 6]]) == [[[1 2] [3 4] [5 6]] [[1 2] [3 4]] [[1 2] [5 6]] [[1 2]] [[3 4] [5 6]] [[3 4]] [[5 6]] []] When I first looked at the lisp version of this, I had no idea it had three different return points. Explicit is better than implicit. ;-) So how does that anything like byte code? The structure is just nested tokens and symbols. (This will parse and evaluate fine in this form ... with the comments too.) def # keyword "power-set set" # string-literal [ # block-start if # keyword ( # expression-start is-empty # name set # name ) # expression-stop [ # block-start return # keyword ( # expression-start list # name set # name ) # expression-stop ] # block-stop .... etc. There's a bit more... python wrappers for dictionaries, and sets, and lower level functions. I was thinking of rewriting it in C and seeing how it performs, but Gambit-C may be a better choice. It has nearly all the low level features python needs and compiles to C or Java. So don't hold your breath. It will be a while before I can get that far. :-) Cheers, Ron