Since these discussions are uselessly abstract and meta
Here is some code I (tried) to write in class the other day
The basic problem is of generating combinations
Using the pascal-identity nCr + nC(r-1) = (n+1)Cr
This can be written (Haskell)
c :: Int -> Int -> Int
c n 0 = 1
c 0 (r+1) = 0
c (n+1) (r+1) = c n r + c n (r+1)
But I dont want NUMBER of combinations I want to generate combinations from
a given set
So change the spec to
c :: [a] -> Int -> [[a]]
ie n stops being a number but is now a set (here list) length n
c n 0 = [[]]
c [] (r+1) = []
c (x:xs) (r+1) = [x:l | l <- c xs r] ++ c xs (r+1)
Runs
? c [1,2,3,4] 2
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] :: [[Int]]
All binomials
? [c [1,2,3,4] r | r <- [0..4]]
[
[[]],
[[1], [2], [3], [4]],
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]],
[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]],
[[1, 2, 3, 4]]
] :: [[[Int]]]
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:
st = frozenset
nullset = st([])
def singleton(x): return st([x])
def splitset(s):
i = iter(s)
e = next(i)
new = st(i)
return e,new
def cs(n,r):
""" Set version of c"""
if r == 0 :
return singleton(nullset)
elif len(n) == 0 :
return nullset
else:
x,xs = splitset(n)
return st([(singleton(x) | l) for l in cs(xs,r-1)]) | cs(xs,r)
def ss0n(fs):
""" Shows a simple-set (ie set-0, contains no subsets) nicely"""
r = "{"
for x in fs:
r += repr(x) + ", "
return r + "}"
def ss1n(fs0):
""" Shows a set-of-sets (ie set-1, contents are sets) nicely"""
r = "{"
for x in fs0:
r += ss0n(x) + ", "
return r + "}"
>>> cs({1,2,3,4}, 2)
frozenset([frozenset([2, 4]), frozenset([3, 4]), frozenset([2, 3]),
frozenset([1, 3]), frozenset([1, 2]), frozenset([1, 4])])
>>> ss1n(cs({1,2,3,4}, 2))
'{{2, 4, }, {3, 4, }, {2, 3, }, {1, 3, }, {1, 2, }, {1, 4, }, }'
>>> ss1n(cs({1,2,3,4}, 2))
'{{2, 4, }, {3, 4, }, {2, 3, }, {1, 3, }, {1, 2, }, {1, 4, }, }'
So how could this be done better?
Here for reference is an abstract math ideal I would like to approximate
c : {t} → Int → {{t}} ## t is an arbitrary unspecified type
c n 0 = {{}}
c {} (r+1) = {}
c ({x} ∪ xs) (r+1) = {{x} ∪ l | l ∈ c xs r} ∪ c xs (r+1)
exactly parallel to the pascal identity
c n 0 = 1
c 0 (r+1) = 0
c (n+1) (r+1) = c n r + c n (r+1)
--
https://mail.python.org/mailman/listinfo/python-list
