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