Permutation generator on C

Question

I need a simple Algorithm of permutation generator which could be apply on simple C language.

Answer 1

Here is a simple recursive solution to produce all permutations of a set of characters passed on the command line:

#include <stdio.h>
#include <string.h>

int perm(const char *src, int len, char *dest, char *destbits, int n) {
    if (n == len) {
        printf("%.*s\n", len, dest);
        return 1;
    } else {
        int count = 0;
        for (int i = 0; i < len; i++) {
            if (destbits[i] == 0) {
                destbits[i] = 1;
                dest[n] = src[i];
                count += perm(src, len, dest, destbits, n + 1);
                destbits[i] = 0;
            }
        }
        return count;
    }
}

int main(int argc, char *argv[]) {
    const char *src = (argc > 1) ? argv[1] : "123456789";
    int len = strlen(src);
    char dest[len], destbits[len];

    memset(destbits, 0, sizeof destbits);
    int total = perm(src, len, dest, destbits, 0);
    printf("%d combinations\n", total);

    return 0;
}

Answer 2

Permutes over numbers:

In order to do use each permutation, you have to hook up to the print function.

#include <stdio.h>
#include <stdlib.h>

/**
   Read a number, N, from standard input and print the
   permutations.
 */

void print(const int *v, const int size)
{
  if (v != 0) {
    for (int i = 0; i < size; i++) {
      printf("%4d", v[i] );
    }
    printf("\n");
  }
} // print


void swap(int *v, const int i, const int j)
{
  int t;
  t = v[i];
  v[i] = v[j];
  v[j] = t;
}


void rotateLeft(int *v, const int start, const int n)
{
  int tmp = v[start];
  for (int i = start; i < n-1; i++) {
    v[i] = v[i+1];
  }
  v[n-1] = tmp;
} // rotateLeft


void permute(int *v, const int start, const int n)
{
  print(v, n);
  if (start < n) {
    int i, j;
    for (i = n-2; i >= start; i--) {
      for (j = i + 1; j < n; j++) {
    swap(v, i, j);
    permute(v, i+1, n);
      } // for j
      rotateLeft(v, i, n);
    } // for i
  }
} // permute


void init(int *v, int N)
{
  for (int i = 0; i < N; i++) {
    v[i] = i+1;
  }
} // init


int main()
{
    int *v = (int*) malloc(sizeof(int)*10);
    init(v, 10);
    permute(v, 0, 10);
    free(v);
}

Answer 3

I'm looking for something more iteractive, then I implement my poor version. I can see some optimizations, but for now it's helps me. I hope this helps anyone.

#include <stdio.h>
#include <stdlib.h>

#define PERM_T int
#define PERM_T_PFLAG "%d"

void swap(PERM_T *array, int i, int j) {
  PERM_T aux = array[i];
  array[i] = array[j];
  array[j] = aux;
}

void print_array_perm(PERM_T *array, int n) {
  printf("[");
  n -= 1;
  for (int i = 0; i < n; i++) {
    printf(PERM_T_PFLAG", ", array[i]);
  }
  if (n >= 0)
    printf(PERM_T_PFLAG, array[n]);
  printf("]\n");
}

void print_array_int(int *array, int n) {
  printf("[");
  n -= 1;
  for (int i = 0; i < n; i++) {
    printf("%d, ", array[i]);
  }
  if (n >= 0)
    printf("%d", array[n]);
  printf("]\n");
}

void copy_array_T(
  PERM_T *src, PERM_T *dst,
  int start, int end) {
  for (int i = start; i < end; i++) {
    dst[i] = src[i];
  }
}

void copy_array_int(
  int *src, int *dst,
  int start, int end) {
  for (int i = start; i < end; i++) {
    dst[i] = src[i];
  }
}

void rotate_array(
  PERM_T *array,
  int start, int end) {
  PERM_T aux = array[start];
  copy_array_T(
    array + 1, array, start, end);
  array[end - 1] = aux;
}

int factorial(int n) {
  int result = 1;
  while (n > 1) {
    result *= n;
    n--;
  }
  return result;
}

typedef struct {
  PERM_T *data;
  int length;
  int *ks;
  int kn;
  int _i;
} Perm;

Perm perm_(
  PERM_T *data, PERM_T *array, int n) {
  copy_array_T(array, data, 0, n);
  int kn = n > 1 ? n - 1 : 0;
  
  int *ks = kn
    ? malloc(sizeof(PERM_T) * kn)
    : NULL;
  for (int i = 0; i < kn; i++)
    ks[i] = i;

  int max_iterations = factorial(n);
  Perm p = {
    .data = data,
    .length = n,
    .ks = ks,
    .kn = kn,
    ._i = max_iterations
  };
  return p;
}

Perm perm(PERM_T *array, int n) {
  PERM_T *data = 
    malloc(sizeof(PERM_T) * n);
  return perm_(data, array, n);
}

Perm copy_perm(Perm p) {
  Perm copy = perm(p.data, p.length);
  copy_array_int(p.ks, copy.ks, 0, p.kn);
  return copy;
}

void clear_perm(Perm* p) {
  free(p->data);
  if (p->kn) free(p->ks);
}

int completed_perm(Perm *p) {
  return p->_i < 1;
}

void next_perm_self(Perm *p) {
  int n = p->length;

  if (completed_perm(p)) return;

  p->_i--;
  int k = p->kn - 1;
  int *ks = p->ks;
  PERM_T *data = p->data;

  if (ks[k] + 1 != n) {
    rotate_array(data, k, n);
    ks[k] += 1;
  } else {
    while (k >= 0 && ks[k] + 1 == n) {
      ks[k] = k;
      rotate_array(data, k, n);
      k -= 1;
    }
    if (k >= 0) {
      rotate_array(data, k, n);
      ks[k] += 1;
    }
  }
}

Perm next_perm_(Perm *p) {
  Perm next = copy_perm(*p);
  next_perm_self(&next);
  return next;
}

Perm next_perm(Perm *p) {
  Perm next = next_perm_(p);
  clear_perm(p);
  return next;
}

void print_perm(Perm p) {
  print_array_perm(p.data, p.length);
}

void print_perm_(Perm p) {
  printf("%p\n", p.data);
  print_perm(p);
  print_array_int(p.ks, p.kn);
}

Perm next_print(Perm *p) {
  print_perm(p);
  return next_perm(p);
}

void next_print_self(Perm *p) {
  print_perm(*p);
  next_perm_self(p);
}

int main() {
  int a1[] = {1,2,3,4,5};
  Perm p = perm(a1, 5);
  
  int i = 0;
  while (!completed_perm(&p)) {
    printf("%3d ", i++);
    // p = next_print(&p);
    next_print_self(&p);
  }

  clear_perm(&p);
  return 0;
}