列出所有 1...n 的子集
from pprint import pprint as print
def subsets(n):
assert(n >= 0)
s = []
r = []
def h(n):
if n == 0:
r.append(s[:])
else:
s.append(n)
h(n - 1)
del s[-1]
h(n - 1)
h(n)
return r
print(subsets(3))
輸出
[[3, 2, 1], [3, 2], [3, 1], [3], [2, 1], [2], [1], []]
從 1...n 選 m 個數(shù)舔腾，列出所有組合
from pprint import pprint as print
def combinations(n, m):
assert(n >= 0 and m >= 0)
c = []
r = []
def h(n, m):
if n >= m:
if m == 0:
r.append(c[:])
else:
c.append(n)
h(n - 1, m - 1)
del c[-1]
h(n - 1, m)
h(n, m)
return r
print(combinations(5, 3))
輸出
[[5, 4, 3],
[5, 4, 2],
[5, 4, 1],
[5, 3, 2],
[5, 3, 1],
[5, 2, 1],
[4, 3, 2],
[4, 3, 1],
[4, 2, 1],
[3, 2, 1]]
從 1...n 選 m 個數(shù)，列出所有排列
from pprint import pprint as print
def permutations(n, m):
assert(n >= 0 and m >= 0)
p = []
r = []
def h(n, m):
if m == 0:
r.append(p[:])
else:
for i in range(1, n + 1):
if not i in p:
p.append(i)
h(n, m - 1)
del p[-1]
h(n, m)
return r
print(permutations(5, 2))
輸出
[[1, 2],
[1, 3],
[1, 4],
[1, 5],
[2, 1],
[2, 3],
[2, 4],
[2, 5],
[3, 1],
[3, 2],
[3, 4],
[3, 5],
[4, 1],
[4, 2],
[4, 3],
[4, 5],
[5, 1],
[5, 2],
[5, 3],
[5, 4]]
