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

/**
 * Prints permutations of 1...n, where n is given as a command-line
 * argument.
 *
 * @author Jim Glenn
 * @version 0.1 2018-09-25 pneumonia free!
 */

/**
 * Prints the permutations of the values in the given array that start
 * with the current prefix of the given length.
 *
 * @param p a pointer to an array of ints, non-NULL
 * @param prefix_len the length of the prefix
 * @param n the length of the array
 */
void print_permutations(int *p, int prefix_len, int n);

int main(int argc, char *argv[])
{
  int n = 1;
  if (argc >= 2)
    {
      n = strtol(argv[1], NULL, 10);
      if (n <= 0)
	{
	  fprintf(stderr, "%s: invalid n %s\n", argv[0], argv[1]);
	  return 1;
	}
    }

  int *p = malloc(sizeof(int) * n);
  if (p == NULL)
    {
      fprintf(stderr, "%s: memory allocation failed\n", argv[0]);
      return 1;
    }
  for (int i = 0; i < n; i++)
    {
      p[i] = i + 1;
    }
  
  print_permutations(p, 0, n);

  free(p);
}


void print_permutations(int *p, int prefix_len, int n)
{
  if (prefix_len == n)
    {
      // we have a complete permutation -- print it!
      for (int i = 0; i < n; i++)
	{
	  printf("%d%s", p[i], i < n - 1 ? " " : "\n");
	}
    }
  else
    {
      // for each possible next item in the permutation
      // add it
      // recurse on the now-longer partial permutation
      // remove it
      for (int i = prefix_len; i < n; i++)
	{
	  // add it = swap to end of partial permutation
	  int temp = p[prefix_len];
	  p[prefix_len] = p[i];
	  p[i] = temp;
	  prefix_len++;

	  // recurse
	  print_permutations(p, prefix_len, n);

	  // remove it = unswap
	  prefix_len--;
	  temp = p[prefix_len];
	  p[prefix_len] = p[i];
	  p[i] = temp;	  
	}
    }
}