All permutations of array where each element in the array must be increasing by range between 0 and n

Question

Let's say I have a list of elements with values

[1, 2, 3, 5, 6, 7, 9, 12]

Basically, the elements in the array may max have a difference of n, in this case three, in increasing order.

The array above would work like:

2-1 = 1 | difference of 1
3-2 = 1 | difference of 1
5-3 = 2 | difference of 2
6-5 = 1 | difference of 1

And so on. How would I go about to find all permutations of an array with length x and a max difference of n?

Answer 1

Assuming you are looking for differences in absolute value, you can do this recursively by progressively adding each eligible element to the result:

here's an example using a recursive generator function:

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))

Output

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]