The fastest way to get all permutations of a range without having consecutive neighbours in python

Question

I want to get all permutations of any range with length n, starting from 0 and ending on n (range(n)) that don't have consecutive numbers.

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

There the permutations should look like for example [0,2,4,1,3] or [3,1,4,2,0]

My current approach just gets all existing permutations and just skips these ones that have consecutive numbers in them.:

import itertools
all = itertools.permutations(range(n))
  
for e in all:
  double = True
      
  for a, b in zip(e, e[1:]):
    if abs(int(a)-int(b)) <= 1:
      double = False
      break

    if double == True:
      # do sth

the problem I have with this code is that the number of permutations rises by a lot really fast and when it comes to ranges of 10 or bigger, I spend most of my time just skipping permutations and waisting time. Is there any way to do this more efficiently?

And another question: If that can be done faster, is there then also a more time efficient implementation where the elements must be at least 2 units appart? That the line if abs(int(a)-int(b)) <= 1 is changed to if abs(int(a)-int(b)) <= 2 and only permutations like [0,4,1,5,2,6,3] are accepted?

Answer 1

The following recursive function does the trick. It constructs only the wanted permutations. It accepts a dst argument indicating the minimum distance that must be exceeded by the next addition taken from set rem to the end of list beg.

# 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], ...]

The for-loop checks for every potential addition num whether the distance between it and the last element of beg is bigger than dst. If beg is the empty list (not beg), no such check is necessary.

Here is how it is intended to be used in full generality:

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

---

Calling

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

prints the following:

[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]

Calling

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

prints the following:

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

Your desired example [0,4,1,5,2,6,3] is in the results for 7 numbers with dst set to 2:

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

Enlarging the set of numbers to permute leads quickly to long lists:

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

---

By the way, the answer by Andrej Kesely makes excellent use of yield.