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'
--
https://mail.python.org/mailman/listinfo/python-list
