''' This code attempts to find a counter-example to the assertion that, for arrays with 4 or more elements, it is ALWAYS possible to turn the array into a sorted array... Problem statement from codechef weekly contest: Anti Adjacent Swaps You are given an array of N elements. In one operation you can swap any two elements if they are not adjacent. That is, you can pick two indices i and j (1 <= i < j <= N) such that j-i > 1, and swap the elements at i and j. Using this operation finitely many (possibly, zero) times, is it possible to turn the array into a sorted array? Check out the full question here: https://www.codechef.com/problems/ANADSW ''' from itertools import count from random import randint,sample # Create 4-6 integer arrays (lists) arrays = tuple(sample(range(1000), k=randint(4,6)) for _ in range(50)) print(f'Solving for these {len(arrays)}' ' random arrays:', *(' '.join(f'{el:4}' for el in a) for a in arrays),sep='\n') # Output counter counter = count(1) # Do 50 iterations for A in arrays: N = len(A) S = sorted(A) # Our goal # Used to collect sequence of swaps sequence = [tuple(A)] changes = [] # formatting # Separate the iterations print(f'#{next(counter)}') # Randomly (but legally) swap elements # until the array is sorted while A != S: # Select indexes that meet swap # criteria defined above i = randint(0,N-3) j = randint(i+2,N-1) # Swap elements A[i],A[j] = A[j],A[i] # This part ensures we don't print a # result with the same sequence in it # more than once a = tuple(A) if a in sequence: # Clean out everything after the last # value of A that matched the current # array sequence = sequence[ :sequence.index(a) + 1 ] changes = changes[ :len(sequence) - 1 ] # formmatting else: # Add this new sequence sequence.append(a) changes.append((i,j)) # formatting # Print the sequence of swaps print(*(f'{n:4}' for n in sequence[0])) for A,ij in zip(sequence[1:],changes): print(*(f'{A[i]:4}' if i in ij else f'{A[i]:4}' for i in range(len(A))), flush=True) # Made it through all iterations print('\nAll Finished') # formatting open('.png','w').write('') print(''' ''')

Restricted Swaps