给定一组n项，我想生成所有可以从该组中选择（替换）的方法k次，以使顺序很重要，并且每个元素至少使用一次。因此k> = n可以进行任何有效的排列。如果k = n，这只是一个排列。所以k> n有点像排列的扩展，但是我不知道它叫什么。
当然，获得一种算法很容易，尽管速度很慢：只需遍历所有可能的选择，然后将没有每个元素的选择至少扔一次。因此，要使某项事情变得高效，将需要类似于迭代排列的技巧，或者将其分解为子问题，在这些子问题中，我们可以直接使用现有的排列算法。
我试图通过使用python进行以下类似的操作来将其分解为排列和组合问题。
import itertools
def func(inputSet,k):
n = len(inputSet)
assert(k>n)
# first, guarantee we have each element once
for p in itertools.permutations(inputSet):
# now select (k-n) locations to insert other elements
for c in itertools.combinations_with_replacement(range(n+1),k-n):
insertions = [c[i]+i for i in range(len(c))]
out = list(p)
for index in insertions:
out.insert(index,0)
# now select values to put in those locations
for vals in itertools.product(inputSet,repeat=len(insertions)):
for i in xrange(len(insertions)):
out[c[i]] = vals[i]
yield tuple(out)
但是，不同的插入可以产生相同的结果，因此，此第一个刺伤可能无法沿着正确的路径开始。我可以添加条件来检查这些情况并过滤掉一些结果，但是用于组合迭代问题的算法（可能需要过滤）可能不是最有效的算法。
这个“排列扩展名”是否有名称？
什么是迭代安排的有效算法？
所谓的排列与排列相同，只是框架略有不同。考虑元素P的集合，您实际上是在要求与P的（kn）个元素联合生成集合P中的所有排列，可以通过itertools.combinations_with_replacement找到。
要生成实际的排列，您可以使用list(set(itertools.permutations))或more_itertools.distinct_permutations：https : //more-itertools.readthedocs.io/en/latest/api.html#more_itertools.distinct_permutations
将其放入实际代码中
>>> x = [1,2,3]
>>> k = 5
>>> results = set()
>>> for y in itertools.combinations_with_replacement(x, k - len(x)):
... for z in itertools.permutations(x + list(y)):
... results.add(z)
...
>>> results
set([(1, 1, 1, 2, 3), (1, 3, 3, 1, 2), (1, 2, 3, 3, 2), (3, 3, 2, 1, 3), (1, 3, 3, 2, 2), (1, 1, 2, 2, 3), (3, 1, 2, 3, 2), (1, 1, 3, 2, 3), (1, 3, 1, 2, 2), (1, 2, 2, 1, 3), (3, 2, 1, 2, 2), (3, 1, 2, 1, 2), (3, 2, 1, 3, 1), (3, 1, 1, 3, 2), (2, 3, 3, 2, 1), (1, 2, 1, 3, 3), (3, 1, 2, 3, 3), (2, 3, 2, 1, 1), (2, 3, 2, 2, 1), (1, 2, 2, 3, 3), (2, 1, 3, 2, 3), (2, 2, 2, 3, 1), (1, 3, 2, 2, 3), (2, 3, 3, 1, 1), (1, 2, 1, 1, 3), (3, 2, 2, 1, 1), (2, 1, 2, 2, 3), (2, 2, 1, 3, 1), (1, 3, 3, 2, 3), (2, 3, 3, 1, 3), (3, 2, 3, 2, 1), (3, 2, 3, 1, 1), (2, 1, 1, 2, 3), (3, 3, 1, 1, 2), (3, 2, 2, 2, 1), (2, 2, 3, 2, 1), (1, 3, 1, 2, 3), (2, 2, 3, 1, 2), (3, 1, 2, 1, 3), (2, 1, 1, 3, 3), (3, 3, 2, 2, 1), (1, 1, 2, 3, 1), (1, 2, 2, 3, 2), (3, 2, 1, 1, 2), (2, 1, 3, 2, 2), (1, 3, 2, 2, 2), (3, 1, 1, 1, 2), (3, 3, 2, 1, 1), (2, 3, 3, 1, 2), (3, 2, 1, 3, 2), (1, 2, 1, 3, 1), (2, 3, 1, 2, 3), (1, 2, 3, 2, 1), (3, 1, 3, 1, 2), (3, 3, 1, 2, 2), (1, 2, 3, 1, 1), (2, 2, 1, 1, 3), (2, 1, 1, 3, 2), (1, 1, 2, 3, 2), (3, 2, 1, 1, 3), (2, 1, 3, 2, 1), (2, 1, 1, 3, 1), (1, 3, 2, 2, 1), (1, 3, 2, 1, 1), (3, 2, 2, 1, 3), (2, 2, 3, 3, 1), (3, 1, 1, 2, 1), (2, 2, 1, 3, 3), (1, 3, 3, 2, 1), (3, 2, 3, 1, 2), (3, 1, 2, 3, 1), (2, 2, 2, 1, 3), (1, 1, 3, 1, 2), (1, 1, 2, 1, 3), (2, 1, 3, 3, 2), (3, 3, 1, 2, 3), (1, 3, 2, 3, 2), (3, 3, 2, 3, 1), (3, 1, 3, 2, 2), (2, 1, 3, 1, 1), (1, 1, 2, 3, 3), (2, 1, 3, 1, 2), (1, 3, 2, 1, 2), (1, 2, 1, 2, 3), (3, 2, 2, 1, 2), (3, 1, 1, 2, 2), (2, 2, 1, 3, 2), (2, 3, 2, 3, 1), (1, 1, 1, 3, 2), (2, 3, 1, 2, 1), (1, 2, 3, 1, 3), (2, 3, 1, 1, 1), (1, 2, 3, 2, 3), (2, 1, 2, 3, 3), (3, 2, 1, 2, 3), (1, 2, 2, 2, 3), (3, 2, 1, 2, 1), (2, 1, 1, 1, 3), (1, 3, 2, 3, 3), (1, 1, 3, 3, 2), (3, 2, 2, 3, 1), (3, 1, 3, 2, 3), (2, 1, 2, 1, 3), (1, 3, 3, 3, 2), (3, 2, 3, 3, 1), (2, 2, 3, 1, 3), (3, 2, 1, 1, 1), (2, 1, 3, 1, 3), (1, 2, 1, 3, 2), (3, 3, 1, 3, 2), (1, 3, 2, 1, 3), (2, 3, 1, 3, 2), (3, 1, 1, 2, 3), (2, 3, 3, 3, 1), (1, 1, 3, 2, 1), (2, 3, 1, 1, 2), (1, 2, 3, 2, 2), (2, 1, 2, 3, 2), (1, 3, 1, 1, 2), (3, 1, 3, 3, 2), (3, 1, 2, 2, 2), (3, 3, 1, 2, 1), (3, 3, 3, 1, 2), (3, 2, 3, 1, 3), (1, 3, 1, 3, 2), (2, 3, 2, 1, 3), (2, 1, 3, 3, 3), (1, 2, 2, 3, 1), (2, 3, 1, 3, 3), (1, 2, 3, 3, 1), (2, 3, 1, 2, 2), (3, 3, 2, 1, 2), (2, 3, 1, 3, 1), (3, 2, 1, 3, 3), (1, 1, 3, 2, 2), (2, 3, 1, 1, 3), (2, 1, 2, 3, 1), (1, 2, 3, 3, 3), (1, 3, 1, 2, 1), (3, 1, 2, 2, 3), (3, 1, 2, 2, 1), (2, 1, 3, 3, 1), (3, 1, 2, 1, 1), (1, 3, 2, 3, 1), (1, 2, 3, 1, 2), (3, 1, 3, 2, 1), (2, 2, 1, 2, 3), (2, 3, 2, 1, 2), (3, 3, 3, 2, 1), (2, 2, 3, 1, 1)])
请注意，这组合起来会很快爆炸，但是由于同时生成器itertools.combinations_with_replacement和itertools.permutations返回生成器，您也可以yield得到结果。您也可以递归地编写它，但是我个人认为这并不令人满意。
我相信distinct_permutations在这里使用它也足够了，您将得到一个完全不同的结果列表，因为外循环的每次迭代都会导致元素的频率签名不同。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句