sets anomaly

Rustom Mody rustompmody at gmail.com
Wed Dec 7 10:17:53 EST 2016


Trying to write some code using sets (well frozen sets)
And was hit by this anomaly

This is the behavior of lists I analogously expect in sets:

>>> []
[]
>>> [[]]
[[]]
>>> 

ie the empty list and the list of the empty list are different things

However
(with
f= frozenset
)

>>> f()
frozenset()
>>> f([])
frozenset()
>>> f(f([]))
frozenset()
>>> 

Spent a good ½ hour finding out this strangeness
And then some figuring out how to get an empty set into a set
This is the best I get:
>>> f([f([])])
frozenset({frozenset()})

Context:


Trying to write the simple combinatorics code which does the enumeration 
corresponding to the identity:
ⁿCr + ⁿCr-1 = ⁿ⁺¹Cr

The Haskell code is very simple:
[`c` means function c used in infix]

[]      `c` (r+1) = []
xs      `c` 0	  = [[]]
(x::xs) `c` r	  = (xs `c` r) ++ [x::ys | ys <- xs `c` (r-1)]


And its usage:
? [1,2,3,4] `c` 2
[[3, 4], [2, 4], [2, 3], [1, 4], [1, 3], [1, 2]] : [[Int]]

I wanted to do it in python to discuss the question of sets and lists

The best I get is this. 

Can it be improved??


-------------------------------
f = frozenset

def c(zs,r):
    """ returns list of lists """
    if not zs and r > 0 : return []
    if r == 0 : return  [[]]
    x,xs = zs[0], zs[1:]
    return c(xs,r) + [[x]+ys for ys in c(xs,r-1)]

def css(zs,r):
    """ returns set of sets """
    if not zs and r > 0 : return f([])
    if r == 0 : return  f([f([])])
    x,xs = zs[0], zs[1:]
    return css(xs,r) | f([(f([x]) | ys) for ys in css(xs,r-1)])

def cls(zs,r):
    """ returns list of sets """
    if not zs and r > 0 : return []
    if r == 0 : return  [f([])]
    x,xs = zs[0], zs[1:]
    return cls(xs,r) + [f([x]) | ys for ys in cls(xs,r-1)]

And usage:

>>> c("ABC",2)
[['B', 'C'], ['A', 'C'], ['A', 'B']]
>>> css("ABC",2)
frozenset({frozenset({'C', 'A'}), frozenset({'C', 'B'}), frozenset({'B', 'A'})})
>>> cls("ABC",2)
[frozenset({'C', 'B'}), frozenset({'C', 'A'}), frozenset({'B', 'A'})]


More information about the Python-list mailing list