Please improve these comprehensions (was meaning of [ ])

[Rustom Mody]

On Tuesday, September 5, 2017 at 1:44:24 AM UTC+5:30, Ben Bacarisse wrote:
> Rustom Mody  writes:
> 
> > Here is some code I (tried) to write in class the other day
> >
> > The basic problem is of generating combinations
> <snip>
> > Now thats neat as far as it goes but combinations are fundamentally sets
> > not lists
> >
> > So I thought python would do a better job
> > I tried translating it to python and sets but it turned out more annoying than
> > helpful
> > Can someone improve it??
> >
> > The straightforward translation of the above
> > Which is ok so far
> >
> >
> > def c(n,r):
> >     if r == 0:
> >         return [[]]
> >     elif len(n) == 0:
> >         return []
> >     else:
> >         return [[n[0]] + l for l in c(n[1:],r-1)] + c(n[1:],r)
> >
> >
> > Now to go from returning list of lists to set of sets:
> 
> def cs(n, r):
>     if r == 0:
>         return [set()]
>     elif len(n) == 0:
>         return []
>     else:
>         return [set([n[0]]) | l for l in cs(n[1:], r-1)] + cs(n[1:], r)
> 
> ?
> 
> It's not so neat if you also want n to be a set rather than a list
> because the set equivalents of n[0] and n[1:] are a but more complex but
> it's not that bad:
> 
> def css(n,r):
>     if r == 0:
>         return [set()]
>     elif len(n) == 0:
>         return []
>     else:
>         rest = n.copy()
>         e = rest.pop()
>         return [set([e]) | l for l in css(rest, r-1)] + css(rest, r)

Trying out your code Ben…

>>> css({1,2,3,4}, 2)
[set([1, 2]), set([1, 3]), set([1, 4]), set([2, 3]), set([2, 4]), set([3, 4])]

>>> type(css({1,2,3,4}, 2))
<type 'list'>


Whereas with the cs I earlier gave:
>>> cs(frozenset([1,2,3,4]), 2)
frozenset([frozenset([2, 4]), frozenset([3, 4]), frozenset([2, 3]), frozenset([1, 3]), frozenset([1, 2]), frozenset([1, 4])])
>>> type(cs(frozenset([1,2,3,4]), 2))
<type 'frozenset'>

So in case I did not make it clear enough earlier, there are three collection types in the spec.

A small amount of meta-combinatorics on the combinatorics!

Lets say 
{1,2} : ℘ Int  ## powerset 
[1,2] : ℒ Int  ## list type constructor
There are many others eg
⟆1,2⟅ : ℬ Int  ## Bag type constructor
Not to mention iterators
Lets just stay with set and list for simplicity

So the combinations enumerator has the general type (schema)
[For ℛ being one of the above collection type constructors] 
c : ℛ t → Int → ℛ ℛ t

However each of these ℛ's could be different
c : ℛ₁ t → Int → ℛ₂ ℛ₃ t

This gives 8 possibilities (assuming 2 constructors)
Your function had type
css : ℘ t → Int → ℒ ℘ t

whereas I wanted
cs : ℘ t → Int → ℘ ℘ t

And this has not yet touched on the difference between set and frozenset!


Why do we need frozenset at all?
Because the set type wont close in python!

## List of lists... ok
>>> [[1,2],[3,4]]
[[1, 2], [3, 4]]

## List of sets slightly clunky but still ok
>>> [{1,2},{3,4}]
[set([1, 2]), set([3, 4])]

## Set of sets??… Sorry!!
>>> {{1,2},{3,4}}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'set'