排列组合(非递归版)

2020-07-18  本文已影响0人  小幸运Q

https://blog.csdn.net/so_geili/article/details/71078945


方法1:暴力穷举

"1234"被按序分为
(1)已知序列[12,21]
(2)待插入序列["3","4"]
插入3在已知序列i的开头结尾还有数字中间可得已知序列[312,132,123]和待插入序列4

// 递归版

p="1234"
"""
初始res=[p[0]]
针对每个上一轮的string,字符串队尾p[ends]
依次for i=0->ends-1 i=ends插入p[i]前一位得到新的解加入r
res=r
"""
res=set()
res.add(p[0])
def run(p,res,ends):
    if(len(p)==ends+1):
        print(res)
        print(len(res))
        return
    insert=p[ends+1]
    t=set()
    for string in res:
        for i in range(len(string)):
            new_string=string[0:i]+insert+string[i:ends+1]
            t.add(new_string)
        t.add(string+insert)
    run(p,t,ends+1)
run(p,res,0)

// 非递归版
def run(p,res,ends):
    while 1:
        if(len(p)==ends+1):
            print(res)
            print(len(res))
            return
        insert=p[ends+1]
        t=set()
        for string in res:
            for i in range(len(string)):
                new_string=string[0:i]+insert+string[i:ends+1]
                t.add(new_string)
            t.add(string+insert)
        res=t
        ends+=1

方法2:字典序

起点:字典序最小的排列,例如12345

终点:字典序最大的排列,例如54321

过程:从当前排列生成字典序刚好比它大的下一个排列


这里用一个int数组作为例子辅助说明。
[4, 6, 7, 2, 3, 1, 9]

  1. 从小到大排序
  2. 从后往前沿着上坡找,找到第一个下降点i(即右边第一个点比我大)
  3. 确定一个在他右边的数j,比他大,但是又不能太大(在右边所有数字中比它大的里面最小),这样交换带来的增益最小。如果有,则交换i和j。
  4. 对于j,交换后,将[j+1,n]进行逆序(相当于头头换了,尾巴也得重构,原来的上坡最稳定,需要打反方向成下坡,这样最不稳定,需要重新洗牌成为上坡,中间过程即是新排列组合)
k="12321"
p=[]
for i in k:
    p.append(i)

counts=0
# 检查[from,to)之间的元素和第to号元素是否相同
def run(p):
    global counts
    if(len(p)<=1):
        print(p)
        counts=len(p)
        return
    p=sorted(p)
    while 1:
        print(p)
        counts+=1
        for i in range(len(p)-2,-1,-1):
            if(p[i]<p[i+1]):
                #找到i了
                choose=i+1
                for j in range(i,len(p)):
                    if(p[j]>p[i] and p[choose]>=p[j]):
                        # 为了避免出现多个相同的值但是只取从左到右第一个
                        # (实际我们需要取最后一个),所以容许相等也能choose
                        choose=j
                p[choose],p[i]=p[i],p[choose]
                p=p[:i+1]+p[i+1:][::-1]
                break
            if(i==0):
                # 取到字典序最大的退出循环
                return
run(p)
print(counts)

答:参考字典序排序

上一篇下一篇

猜你喜欢

热点阅读