DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

C - Permutation Multiplication

05.17.2007
| 4626 views |
  • submit to reddit
        This code multiplies the permutations given as imput via in. This uses the normal human search and write algorithm. It goes through the input many times.

Example:
In: (acfg)(bcd)(aed)(fade)(bgfae)
Out: (a d g) (c e b) (f)

typedef char str[64];

void pmul_c(str in, str out) {
  int n = strlen(in);
  char *m = (char*)malloc(sizeof(char) * n + 1);
  memset(m, 0, n);
  m[n] = 0;

  int k = 0;
  int i = 0;
  int c;
  for (; i < n; ++i)
    if (in[i] == '(') {
      m[i] = 1;
      c = in[i + 1];
    } else if (in[i] == ')') {
      m[i] = 1;
      in[i] = c;
    }

  char start;
  char curent;
A2:
  i = 0;
  while (m[i] == 1)
    ++i;
  if (i == n)
    return;
  start = in[i];
  out[k++] = '(';
  out[k++] = start;
  m[i] = 1;

A3:
  curent = in[++i];
  ++i;

A4:
  while ((i < n) && (in[i] != curent))
    ++i;
  if (i < n) {
    m[i] = 1;
    goto A3;
  }

  if (curent != start) {
    out[k++] = curent;
    i = 0;
    goto A4;
  }

  out[k++] = ')';
  goto A2;

  out[k] = 0;
}