 # 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