Skip to content

Instantly share code, notes, and snippets.

@breadchris
Last active August 20, 2019 00:55
Show Gist options
  • Save breadchris/c371ca8ad64a82d674710e4d60c6655a to your computer and use it in GitHub Desktop.
Save breadchris/c371ca8ad64a82d674710e4d60c6655a to your computer and use it in GitHub Desktop.
ocaml 99 problems #26 in python
tab_depth = 0
def log(s=None, **kwargs):
global tab_depth
msg = s if s is not None else ", ".join(["{} == {}".format(k, v) for k, v in kwargs.items()])
print("\t" * tab_depth + msg)
def perms(n, l):
global tab_depth
log(n=n, l=l)
if n <= 0:
log(s="returning [ [] ]")
return [ [] ]
else:
if len(l) == 0:
log(s="returning []")
return []
h = l[0]
tl = l[1:]
log(h=h, tl=tl)
tab_depth += 1
with_h = list(map(lambda l: [h] + l, perms(n-1, tl)))
without_h = perms(n, tl)
tab_depth -= 1
return with_h + without_h
# Without debugging
def perms_(n, l):
if n <= 0:
return [ [] ]
else:
if len(l) == 0:
return []
h = l[0]
tl = l[1:]
with_h = list(map(lambda l: [h] + l, perms_(n-1, tl)))
without_h = perms_(n, tl)
return with_h + without_h
print(perms(2, ["a", "b", "c", "d"]))
"""
➜ /tmp python test.py
n == 2, l == ['a', 'b', 'c', 'd']
h == a, tl == ['b', 'c', 'd']
n == 1, l == ['b', 'c', 'd']
h == b, tl == ['c', 'd']
n == 0, l == ['c', 'd']
returning [ [] ]
n == 1, l == ['c', 'd']
h == c, tl == ['d']
n == 0, l == ['d']
returning [ [] ]
n == 1, l == ['d']
h == d, tl == []
n == 0, l == []
returning [ [] ]
n == 1, l == []
returning []
n == 2, l == ['b', 'c', 'd']
h == b, tl == ['c', 'd']
n == 1, l == ['c', 'd']
h == c, tl == ['d']
n == 0, l == ['d']
returning [ [] ]
n == 1, l == ['d']
h == d, tl == []
n == 0, l == []
returning [ [] ]
n == 1, l == []
returning []
n == 2, l == ['c', 'd']
h == c, tl == ['d']
n == 1, l == ['d']
h == d, tl == []
n == 0, l == []
returning [ [] ]
n == 1, l == []
returning []
n == 2, l == ['d']
h == d, tl == []
n == 1, l == []
returning []
n == 2, l == []
returning []
[['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'c'], ['b', 'd'], ['c', 'd']]
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment