子集、组合、排列算法

---

列出所有 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 个数，列出所有组合

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 个数，列出所有排列

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]]