Information wants to be free...

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