Constrained Exchange Sort

Given a permutation of 12 letters ‘A’-‘L’, you are invited to write a program to sort them in ascending order under the following set of constraints: • The only allowed operation is the exchange of letters between two locations (locations are num- bered from 1 to 12). • The letter ‘L’ must be involved in each operation. • The letter ‘L’ at location l1 can be swapped with the letter at location l2 provided l1 l2 = di and floor((l1 − 1)/di+1) = floor((l2 − 1)/di+1) for i = 1,2,3, where (d1,d2,d3,d4) = (1,3,6,12). • You must use the minimum number of exchange operations possible. Input The first line of the input file contains an integer representing the number of test cases to follow. Each test case contains a permutation of the letters ‘A’-‘L’ on a line by itself. It is guaranteed that the given permutation can be sorted in ascending order under the given set of constraints. Output For each test case first output the permutation number on a line by itself. The next line will contain a sequence of letters where the letter at location i represents the letter with which ‘L’ is swapped in the i-th exchange during the sorting process. Output an empty line after each test case. Sample Input 2 BKLAIGFHEDCJ LIFDHJAKEGCB Sample Output Permutation #1 EHCJGIKCJGIECBADFJGFJGHIFKEF Permutation #2 AKIHCBJCBJEFCEFIKGJKHBEF