[Python-ideas] Another "little" combination, permutation, iterator, yield from, example.

[Ron Adam]

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