问题
从n个元素中挑选m个元素进行排列,每个元素最多可重复r次。其中m∈[2,n],r∈[1,m]。
如:从4个元素中挑选3个元素进行排列,每个元素最多可重复r次。
分析
解x的长度是固定的,为m。
对于解x,先排第0个位置的元素x[0],再排第1个位置的元素x[1]。我们把后者看作是前者的一种状态,即x[1]是x[0]的一种状态!!
一般地,把x[k]看作x[k-1]的状态空间a中的一种状态,我们要做的就是遍历a[k-1]的所有状态。
那么,套用子集树模板即可。
代码
'''
选排问题
从n个元素中挑选m个元素进行排列,每个元素最多可重复r次。其中m∈[2,n],r∈[1,m]。
作者:hhh5460
时间:2017年6月2日 09时05分
声明:此算法版权归hhh5460所有
'''
n = 4
a = ['a','b','c','d']
m = 3
r = 2
x = [0]*m
X = []
def conflict(k):
global n, r, x, X, a
if x[:k+1].count(x[k]) > r:
return True
return False
def perm(k):
global n,m, a, x, X
if k == m:
print(x)
else:
for i in a:
x[k] = i
if not conflict(k):
perm(k+1)
perm(0)
效果图