通用排列

'''
这个程序不是很有效率，程序中的’if f not in e:‘会产生许多的开销，不是很好，也较难扩展到当L中有重复元素的情况
'''

def permutation_1(L,k):
    def product2(R,L):
        R1=[]
        if R==[[]]:
            for e in L:R1.append([e])
        else:
            for e in R:
                for f in L:
                    if f not in e:
                        R1.append(e+[f])
        return R1
    if k<0 or k> len(L):
        print('k的值应该非负且小于列表长度')
        return []
    if k==0:return [[]]
    R=[[]]
    for i in range(k):
        R=product2(R,L)
    return R


def permutation_2(L,k):
    if k==0:return [[]]
    if len(L)=k:
        T2=permutation_2(L[1:],k)
    if len(L)>=k:
        T1=permutation_2(L[1:],k-1)
    R=[]
    for i in range(k):
        for t in T1:
            # 我写成了t[i:]
            x=t[0:i]+[L[0]]+t[i:k]
            if x not in R:
                R.append(x)
        # for e in T2:
        #     if e not in R:
        #         R.append(e)
    for e in T2:
        if e not in R:
            R.append(e)
    return R


def permutation_dfs(L,k):
    R=[]
    T=[-1 for i in range(k)]
    def P(L,num_pick,m):
        if m>num_pick-1:R.append(T[:])
        else:
            for i in L:
                if i not in T[0:m]:
                    T[m]=i
                    P(L, num_pick, m+1)


    P(L, k, 0)
    return R

L = [ 3, 5, 8]
# res1=permutation_1(L,2)
# print(res1)

# res2=permutation_2(L,2)
# print(res2)

res3=permutation_dfs(L,2)
print(res3)