在 python 中没有连续邻居的情况下获取范围所有排列的最快方法

下面的递归函数可以做到这一点.它只构造想要的排列.它接受dst参数，该参数指示从集合rem到列表beg的末尾的下一个加法必须是exceeded的最小距离.

# comp_perm: complete the permutation
# beg: beginning of sequence
# rem: set of remaining (still unused) numbers
# dst: integer indicating distance that must be *exceeded*
def comp_perm(beg: list, rem: set, dst: int) -> list:
  if (not rem): # check whether rem is the empty set
    return [beg]
  return_lst = [] # list of sequences starting with beg
  for num in rem:
    if (not beg) or abs(num - beg[-1]) > dst:
      return_lst.extend(comp_perm(beg+[num], rem-{num}, dst))
  return return_lst

comp_perm([], set(range(5)), 1)
# [[0, 2, 4, 1, 3], [0, 3, 1, 4, 2], [1, 3, 0, 2, 4], ...]

For循环判断每个可能的加法num与beg的最后一个元素之间的距离是否为bigger than dst.如果beg是空列表(not beg)，则不需要这样的判断.

以下是它的全部通用用法:

comp_perm([5, 9], {7, 11, 100}, 3)
# [[5, 9, 100, 11, 7], [5, 9, 100, 7, 11]]

叫唤

for tpl in comp_perm([], set(range(5)), 1):
  print(tpl)

打印以下内容:

[0, 2, 4, 1, 3]
[0, 3, 1, 4, 2]
[1, 3, 0, 2, 4]
[1, 3, 0, 4, 2]
[1, 4, 2, 0, 3]
[2, 0, 3, 1, 4]
[2, 0, 4, 1, 3]
[2, 4, 0, 3, 1]
[2, 4, 1, 3, 0]
[3, 0, 2, 4, 1]
[3, 1, 4, 0, 2]
[3, 1, 4, 2, 0]
[4, 1, 3, 0, 2]
[4, 2, 0, 3, 1]

叫唤

for tpl in comp_perm([], set(range(6)), 2):
  print(tpl)

打印以下内容:

[2, 5, 1, 4, 0, 3]
[3, 0, 4, 1, 5, 2]

您需要的示例[0,4,1,5,2,6,3]位于7个数字的结果中，其中dst设置为2:

[0,4,1,5,2,6,3] in comp_perm([], set(range(7)), 2)
# True

扩大要置换的数字集很快就会导致长长的列表:

len(comp_perm([], set(range(5)), 2))
# 0
len(comp_perm([], set(range(6)), 2))
# 2
len(comp_perm([], set(range(7)), 2))
# 32
len(comp_perm([], set(range(8)), 2))
# 368

len(comp_perm([], set(range(7)), 3))
# 0
len(comp_perm([], set(range(8)), 3))
# 2
len(comp_perm([], set(range(9)), 3))
# 72
len(comp_perm([], set(range(10)), 3))
# 1496

顺便说一句，answer by Andrej Kesely人很好地利用了yield.