# Permutations by Swapping

A while back, I discovered an algorithm to get all possible permutations (unordered) of a data set, by swapping the elements in a particular way.

I do not know if this is a widely known method, please comment if you have seen this way of finding permutations before.

The swapping sequence is a follows (1-n = swap first element with n-element.):

1-2, 1-3, 1-2, 1-3, 1-2, 1-4, 1-2, 1-3, 1-2, 1-3, 1-2, 1-4, 1-2, ...

To find the element that should be swapped with the first element, the sequence counter/state is divided by the highest possible factorial that will not produce a remainder. Then the basis for the factorial is incremented by one to find the element to swap with.

Example: If the sequence counter is 12, and 12 divided by 3! (3 factorial = 6), there is no remainder. Then the first element needs to be swapped with element 4 (3 + 1) in this iteration of the sequence. If the sequence counter is 13, this is only divisible by 1! and then needs to be swapped with element 2 (1 + 1).

Here is some proof of concept code in C (Note that this algorithm is not recursive, unlike most other permutation algorithms.):

#include <stdio.h> #define SIZE 5 static int numbers[SIZE] = {1, 2, 3, 4, 5}; static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } int main(void) { int i, j, k, temp; int permute_state; /* Print for visualization. (Initial values.) */ for (j = 0; j < SIZE; j++) printf("%d", numbers[j]); printf("\n"); permute_state = 1; for (i = 0; i < factorial(SIZE) - 1; i++) { for (j = SIZE; j > 0; j--) { if (permute_state % factorial(j) == 0) { for (k = 0; k < (j / 2) + 1; k++) { temp = numbers[k]; numbers[k] = numbers[j-k]; numbers[j-k] = temp; } break; } } permute_state++; /* Print for visualization. */ for (j = 0; j < SIZE; j++) printf("%d", numbers[j]); printf("\n"); } return 0; }

*Topic: Scripts and Code, by Kjetil @ 26/10-2008, Article Link*