给定一个集合 A 和一个从 A 到自身的映射 f，寻找元素个数最多的一个自己子集 S ⊆ A S \subseteq A S⊆A，S满足：(1) f 把 S 中每个元素映射到 S 中的另一元素 (即 f 把 S 映射到它自身)，(2) S 中没有两个元素 映射到相同的元素(即 f 在 S 上是一个一对一函数)。
归纳假设假设对于包含 n − 1 n-1 n−1 个元素的集合，如何求解问题是已知的。
归纳证明若集合仅有一个元素，则它必定映射到自己。
假定有一个包含 n 个元素的集合 A，并且要寻找的子集为 S。如果 A 是一对一映射，令 S = A。
若不是，必存在元素 i 没有被任何其他元素映射到。我们断言：i 不可能属于 S。(否则，若 i ∈ S i\in S i∈S 且 S S S 有 k 个元素，则这 k 个元素被映射到至多 k-1 个元素上，从而不可能是一对一的)。因此将 i 从 A 中删去，此时 A 集合只有 n-1 个元素。由归纳假设我们已知如何求解。
由1，2得：对与任意集合，均能完成求解任务。
算法实现def Max_Mapping(A, f): """ V (A的子集) Args:A (list): 给定集合 G (dict): A到自身的映射 """ Count = {a:0 for a in A} V = {} for a in A: Count[f[a]] += 1 V.add(f[a]) while V: a = V.pop() A.remove(a) C[f[a]] -= 1 if C[f[a]] == 0: V.add(f[a])return V
12345678910111213141516171819
