算法竞赛入门第七章(2):枚举排列和子集

可重复集的排列: 有几点要注意

(a): 首先对序列进行排序,然后枚举时候要跳过相同的元素。

(b): 由于存在相同的元素,因此枚举时要判断是否该元素已经全部用完了。

(c): 最后得到的结果是按照字典序从小到大的排列,同时相对以前直接传递参数保存剩下元素的方法来说:空间需求大大减少,但是时间消耗有所增加,当然还有很多可以优化的地方,比如统计元素的出现次数,可以提前计算好。

def do_permuations(P): def perm(P,A,cur): if cur==n:print(A);return item_bef = None for i in range(n): if P[i]==item_bef:item_bef = P[i];continue item_bef = P[i] c1,c2 = 0,0 for j in range(cur): if A[j]==P[i]:c1+=1 for j in range(n): if P[j]==P[i]:c2+=1 if c1<c2: A[cur] = P[i] perm(P,A,cur+1) P = sorted(P) n = len(P) perm(P,[None]*n,0) do_permuations([1,1,1,2])

求解下一个字典序的排列：方法是从右向左寻找，直到发现第一个非递增的元素,然后将这个元素以及其后面的元素进行一次排序,前面的元素排列不变,最后的加起来的结果就是next permutation.

def next_perm(this_p): n = len(this_p) ok=False for i in range(n-1,0,-1): if this_p[i-1]<this_p[i]:ok=True;break if not ok:return None ava = sorted(this_p[i-1:n]) for x in ava: if x>this_p[i-1]: ava.remove(x) this_p[i-1] = x break this_p[i:n] = ava return this_p

利用二进制枚举子集: 相对与增量法,不需要进行定序就可以以极高的效率枚举完成。

def print_subset(array): def do(): for i in range(0, 2**n): for j in range(n): #print('aa\n') if i & (1 << j): print(array[j], end=' ') print() n = len(array) do() print_subset([1, 2, 'sb'])

现在考虑一种复杂一点的情况 ：需要生成子集的集合有重复元素。

为了简单,我们假设集合之间的元素可以进行排序,那么首先进行排序,然后每一次都枚举一个当前最小的元素作为子集的元素。最后要跳过相同的元素。在每添加一改新的元素之后都要输出新的子集。这样就保证不会有重复的子集。

def print_subset2(array): array.sort() def do(s,index): print(s) bef = None for i in range(index, n): if array[i] == bef: continue bef = array[i] s.append(array[i]) do(s, i + 1) s.remove(bef) n = len(array) do([], 0) print_subset2([3,1, 2])

由于上面的方法要求排序 ,如果集合中的元素不方便进行排序,但是是hashable的,那么就可对元素去重,先生成无重复集合的子集,然后将重复的元素添加到生成的子集之中。添加的标准是:添加之后,该元素的个数大于1。仔细想一下,这是为了防止生成重复子集。这是一种将问题转换到熟悉情况的思路。

def print_subset(array): def do(): print() for i in range(1, 2**n): ans = [] for j in range(n): if i & (1 << j): ans.append(array_2[j]) print(ans) if each in ans: for k in range(1, repeat[each] + 1): if k + ans.count(each) > 1: print(ans + [each] * (k)) array_2 = list(set(array)) repeat = {} for each in array: if each not in repeat: repeat[each] = 0 else: repeat[each] += 1 n = len(array_2) do()