By inspection, one possible sequence that satisfies the constraint would be:
1234
1432
3412
4312
1342
3142
4132
4231
2431
3421
4321
2341
3241
1243
2143
4123
1423
2413
4213
3214
2314
1324
3124
2134
1234
At each step there should be just two elements that are exchanged.
For larger N I would recommend you try to implement the Steinhaus–Johnson–Trotter algorithm which I believe will generate these permutations using just swaps of adjacent elements, and will leave you one swap away from the initial position.
Python code based on rosetta code:
N=4
def s_permutations(seq):
def s_perm(seq):
if not seq:
return [[]]
else:
new_items = []
for i, item in enumerate(s_perm(seq[:-1])):
if i % 2:
new_items += [item[:i] + seq[-1:] + item[i:]
for i in range(len(item) + 1)]
else:
new_items += [item[:i] + seq[-1:] + item[i:]
for i in range(len(item), -1, -1)]
return new_items
return [(tuple(item), -1 if i % 2 else 1)
for i, item in enumerate(s_perm(seq))]
for x,sgn in s_permutations(range(1,N+1)):
print ''.join(map(str,x))