Générateur de permutation sur c

Voici une solution récursive simple pour produire toutes les permutations d'un ensemble de caractères transmis sur la ligne de commande:

#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;
}

Je cherche quelque chose de plus itératif, puis je mettez en œuvre ma version médiocre. Je peux voir des optimisations, mais pour l'instant, cela m'aide. J'espère que cela aide tout le monde.

#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;
}