数据结构与算法(二) --- 全排列、全组合

1. (全排列C_{m}^{n})的实现

【要求】输入m,n, 输出所有可能的索引组合

def cmn(m, n):
    if n ==1:
        return [[i] for i in range(1, m+1)]
    elif m==n:
        return [ list(range(1, m+1)) ]
    else:
        temp1 = cmn(m-1, n)
        temp2 = [ i+[m] for i in cmn(m-1, n-1)]
        return temp1 + temp2
    
if __name__ == '__main__':
    print( cmn(5, 2) )

输出：
[[0, 1], [0, 3], [1, 3], [0, 4], [1, 4], [2, 4], [0, 5], [1, 5], [2, 5], [3, 5]]

2. 全部子集

递归

def subsets2(aim):
    # if len(aim) == 1: # 这样不行
    #     return [aim]
    if not aim:
        return [[]]
    else:
        temp1 = subsets2(aim[1:])
        temp2 = [[aim[0]] + i for i in temp1]
        return temp1 + temp2

非递归

def subsets1(nums):
    result = [[]] # 不能result=[]
    for num in nums:
        result += [item + [num] for item in result]
    return result

输出：
[[], [2], [1], [1, 2], [0], [0, 2], [0, 1], [0, 1, 2]]

全排列

class Solution:
    '''
    最简单的办法是：
    from itertools import combinations, permutations
    '''
    def sort_all(self, aim):
        # 全排列
        length = len(aim)
        if length == 0:
            print('空字符串')
            raise TypeError
        elif length == 1:
            return [aim]
        else:
            result = []
            for i in range(length):
                temp = aim[:i] + aim[i+1:]
                for j in self.sort_all(temp) :
                    result.append(aim[i] + j)
            return result