排列组合(非递归版)

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)

• 问：如何交换一个数中的两个数字，使其变成比他大的交换数中最小的哪个。

答：参考字典序排序