排列组合(非递归版)
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]
- 步骤:
- 从小到大排序
- 从后往前沿着上坡找,找到第一个下降点i(即右边第一个点比我大)
- 确定一个在他右边的数j,比他大,但是又不能太大(在右边所有数字中比它大的里面最小),这样交换带来的增益最小。如果有,则交换i和j。
- 对于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)
- 问:如何交换一个数中的两个数字,使其变成比他大的交换数中最小的哪个。
答:参考字典序排序