choose
I'll start with a generic function that takes a list, t, and a number of elements to choose, n -
def choose(t, n):
if n == 0:
return [[]]
elif not t:
return []
else:
return append \
( map \
( choose(rest(t), n - 1)
, lambda c: append([first(t)], c)
)
, choose(rest(t), n)
)
print(choose(["a", "b", "c", "d"], 2))
[['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'c'], ['b', 'd'], ['c', 'd']]
helpers
Your question imposes quite a few restrictions and Python is a multi-paradigm language and so we're going to use a number of helpers to make things readable
def first(t):
return t[0]
def rest(t):
return t[1:]
def append(t0, t1):
return t0 + t1
I don't know if map counts as an import, but we will define our own just in case -
def map(t, f):
if not t:
return []
else:
return append \
( [f(first(t))]
, map(rest(t), f)
)
solve
Great, now that we've finished implementing choose, let's see how we can apply it to our problem
print(choose([5, 4, 8, -3, 6], 2))
[[5, 4], [5, 8], [5, -3], [5, 6], [4, 8], [4, -3], [4, 6], [8, -3], [8, 6], [-3, 6]]
As you can see, we've found all combinations of 2 elements. We just need to loop through these and check if a pair can be subtracted to reach our target, q -
def solve(t, q):
def check(p):
(x, y) = p
return x - y == q or y - x == q
def loop(c):
if not c:
return False
else:
return check(first(c)) or loop(rest(c))
return loop(choose(t, 2))
print(solve([5, 4, 8, -3, 6], 9))
print(solve([-1, 5, 4], 3))
True
False
allowing for
This is a great exercise to build your recursion skills. Disallowing for is the most challenging restriction to overcome. Here's what it could look like if we could use it -
def choose(t, n):
if n == 0:
yield []
elif not t:
return
else:
for c in choose(t[1:], n - 1):
yield [t[0]] + c
yield from choose(t[1:], n)
def solve(t, q):
for (x,y) in choose(t, 2):
if x - y == q or y - x == q:
return True
return False
print(solve([5, 4, 8, -3, 6], 9))
print(solve([-1, 5, 4], 3))
True
False
This variant has an added advantage that it will stop computing combinations as soon as a solution is found. The first variant must compute all combinations first and then begin iterating through them.
allowing other built-ins
Python built-in functions include map and any and offer us another way to get around the for restriction, but I'm unsure if those are allowed -
def choose(t, n):
if n == 0:
yield []
elif not t:
return
else:
yield from map \
( lambda c: [t[0]] + c
, choose(t[1:], n - 1)
)
yield from choose(t[1:], n)
def solve(t, q):
def check(p):
(x,y) = p
return x - y == q or y - x == q
return any(map(check, choose(t, 2)))
print(solve([5, 4, 8, -3, 6], 9))
print(solve([-1, 5, 4], 3))
True
False
