1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
# take-aways:
# - Use integers as lists of boolean values
# - Use 1 << n to compute 2^n where n = len(xs)
def set_from_int(xs, n):
result = []
for i in range(len(xs)):
if n & (1 << i) != 0:
result.append(xs[i])
return result
# subsets :: Set a -> List (Set a)
def subsets(xs):
n = len(xs)
return [set_from_int(xs, i) for i in range(1 << n)]
# 0 1 2
# 0 N Y Y
# 1 _ N Y
# 2 _ _ N
# For my interview, be able to compute *permutations* and *combinations*
# This differs from permutations because this is about finding combinations...
#
# bottom-up
# 0 => { }
# 1 => {3} {4} {3}
# 2 => {5,4} {5,3} {4,3}
xs = [
([], [[]]),
([5], [[], [5]]),
([5,4], [[],[5],[4],[5,4]]),
]
for x, expected in xs:
result = subsets(x)
print("subsets({}) => {} == {}".format(x, result, expected))
assert result == expected
print("Success!")
|
