Cyclic swap – An algorithm to permute in o(1)
It generates in o(1) the next permutation of a string.
Abc
bac
bca ... and so on
This is done by swapping two adjacent digits. The digits to be swapped are incremented every iteration. Swap Indices are applied modulo string length.
Iteration1 – swap arr[0],arr[1]
Iteration2 – swap arr[1],arr[2]
Iteration3 – swap arr[2],arr[0]
1.Generate next permutation of a string in o(1)
2.Work in o(n) memory
3.Infinite iterations –Pseudo code
String string = “abcdef”;
long i,j;
i = j = 0;
while(true)
{
swap(string[i],string[j]);
print string;
i++;
j++;
}
To permute it swaps, to get different permutations, it swaps at different positions.
Will keep on repeating the sequence....exactly in same order
The idea of cyclic swapping can be used in security hardware and software. The output is a function of 'n' th permutation of input bits. The output is a function of first 'n' permutations of input bits... so on lot of crypting functions can be derived.
I applied cyclic swapping to invert a matrix.
Cyclic swapping is useful in
1.Password recovery – Generate all permutaions of password in o(1) time.
2.Matrix inversion
3.Encryption – Use all permutations of input bits to generate maximum diffused output. Order of cyclic swapping is not sorted, hence this will be appropriate here.