假设我有一个带有值的元素列表
[1, 2, 3, 5, 6, 7, 9, 12]
基本上,数组中的元素最大可能具有n的差,在这种情况下为三个,且差值递增。上面的数组将像这样工作:
2-1 = 1 | difference of 1
3-2 = 1 | difference of 1
5-3 = 2 | difference of 2
6-5 = 1 | difference of 1
等等。我将如何找到长度为x且最大差为n的数组的所有排列?
最佳答案
假设您正在寻找绝对值的差异,则可以通过将每个合格元素逐步添加到结果中来递归地执行此操作:
这是使用递归生成器函数的示例:
def permuteSort(A,maxDiff,previous=None):
if not A: yield []; return
for i,a in enumerate(A):
if previous is not None and abs(a-previous) > maxDiff:
continue
yield from ([a]+p for p in permuteSort(A[:i]+A[i+1:],maxDiff,a))
输出for p in permuteSort([1, 2, 3, 5, 6, 7, 9, 12],3):
print(p,"differences:",[b-a for a,b in zip(p,p[1:])])
[1, 2, 3, 5, 6, 7, 9, 12] differences: [1, 1, 2, 1, 1, 2, 3]
[1, 2, 3, 5, 7, 6, 9, 12] differences: [1, 1, 2, 2, -1, 3, 3]
[1, 2, 3, 6, 5, 7, 9, 12] differences: [1, 1, 3, -1, 2, 2, 3]
[1, 2, 5, 3, 6, 7, 9, 12] differences: [1, 3, -2, 3, 1, 2, 3]
[1, 3, 2, 5, 6, 7, 9, 12] differences: [2, -1, 3, 1, 1, 2, 3]
[1, 3, 2, 5, 7, 6, 9, 12] differences: [2, -1, 3, 2, -1, 3, 3]
[2, 1, 3, 5, 6, 7, 9, 12] differences: [-1, 2, 2, 1, 1, 2, 3]
[2, 1, 3, 5, 7, 6, 9, 12] differences: [-1, 2, 2, 2, -1, 3, 3]
[2, 1, 3, 6, 5, 7, 9, 12] differences: [-1, 2, 3, -1, 2, 2, 3]
[3, 1, 2, 5, 6, 7, 9, 12] differences: [-2, 1, 3, 1, 1, 2, 3]
[3, 1, 2, 5, 7, 6, 9, 12] differences: [-2, 1, 3, 2, -1, 3, 3]
[5, 2, 1, 3, 6, 7, 9, 12] differences: [-3, -1, 2, 3, 1, 2, 3]
[6, 3, 1, 2, 5, 7, 9, 12] differences: [-3, -2, 1, 3, 2, 2, 3]
[7, 5, 2, 1, 3, 6, 9, 12] differences: [-2, -3, -1, 2, 3, 3, 3]
[12, 9, 6, 3, 1, 2, 5, 7] differences: [-3, -3, -3, -2, 1, 3, 2]
[12, 9, 6, 7, 5, 2, 1, 3] differences: [-3, -3, 1, -2, -3, -1, 2]
[12, 9, 6, 7, 5, 2, 3, 1] differences: [-3, -3, 1, -2, -3, 1, -2]
[12, 9, 6, 7, 5, 3, 1, 2] differences: [-3, -3, 1, -2, -2, -2, 1]
[12, 9, 6, 7, 5, 3, 2, 1] differences: [-3, -3, 1, -2, -2, -1, -1]
[12, 9, 7, 5, 2, 1, 3, 6] differences: [-3, -2, -2, -3, -1, 2, 3]
[12, 9, 7, 5, 6, 3, 1, 2] differences: [-3, -2, -2, 1, -3, -2, 1]
[12, 9, 7, 5, 6, 3, 2, 1] differences: [-3, -2, -2, 1, -3, -1, -1]
[12, 9, 7, 6, 3, 1, 2, 5] differences: [-3, -2, -1, -3, -2, 1, 3]
[12, 9, 7, 6, 3, 5, 2, 1] differences: [-3, -2, -1, -3, 2, -3, -1]
[12, 9, 7, 6, 5, 2, 1, 3] differences: [-3, -2, -1, -1, -3, -1, 2]
[12, 9, 7, 6, 5, 2, 3, 1] differences: [-3, -2, -1, -1, -3, 1, -2]
[12, 9, 7, 6, 5, 3, 1, 2] differences: [-3, -2, -1, -1, -2, -2, 1]
[12, 9, 7, 6, 5, 3, 2, 1] differences: [-3, -2, -1, -1, -2, -1, -1]
关于python - 数组的所有排列,其中数组中的每个元素必须按0到n之间的范围递增,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65229618/