Exercise: Permutations

The previous exercise, where I asked you to reverse the input recursively, showed how a recursive function can store variables, and how each invocation of the recursive function has its own local variables. And yet, in that example we never made more than one recursive call from each function.

Here, you'll write a recursive function that would call itself multiple times, in a for loop. We will generate and print all permutations of the first n numbers. E.g. for n = 3, it should print

You might notice that the task actually seems recursive. Let's say you iterate the first element of the permutation in the for loop: 1, then 2, then 3. When you are at 1, you have two elements remaining: 2 and 3, and you need to go through all possible permutations of those two elements: 2 3 and 3 2, which gives you 1 2 3 and 1 3 2. Then, for the first element 2, you have 1 and 3 remaining, which gives you 2 1 3 and 2 3 1, and so on.

This gives us the following idea. We will write a function that would accept two arrays: an array where we'll store a permutation, and an array which will mark elements as used, and also our n and the number of elements we have in our permutation already:

void permut(int n, int have, int *result, int *used) {
  ...
}

The initial call will be permut(n, 0, result, used), where result is an array of length at least n, and used is an array of zeros of length n + 1 because we'll mark elements from 1 to n as used, and array indexing starts with 0.

Alternatively, you can use an array of length n and when you use element i, mark used[i - 1], but for me it looks more error prone than just allocating an extra element and use used[i] as a flag.

Each permut will iterate all numbers from 1 to n, and for each of them, if it's not used–that is, if used[i] == 0–it will put the number in result[have], mark the element as used, and call itself with have + 1. The most important thing here is to mark the element as unused again whenever we get back from the recursive call:

for (i = 1; i <= n; ++i) {
  if (!used[i]) {
    used[i] = 1; /* mark as used */
    result[have] = i; /* use it on the current position */
    permut(n, have + 1, ...); /* recursive call */
    used[i] = 0; /* mark as unused */
  }
}

When will it stop? When it's called with have == n, which means that we got n element in our permutation, and we can print whatever we have in result, and return to keep generating more permutations.

There is one problem with printing: we want the elements of the permutations to be separated by a space, but there must be no space after the last element (the tests don't expect that extra space). You will probably need to print either the first or the last element separately, or use a trick people sometimes use in this case:

/* prints ' ' after each element but '\n' after the last one */
printf("%d%c", result[i], i == n - 1 ? '\n' : ' ');

where ... ? ... : ... is a ternary operator, which is an expression that checks if the condition before ? is true, and evaluates either the expression before :, or after :–kind of like an if but in an expression, not a statement, form.

I believe I told you enough so you could try it! Read one number n from the standard input and generate all permutations of 1, 2, ..., n. Since you will need to allocate arrays, let's say that n won't be greater than 8.

#include <stdio.h>

void permut(int n, int have, int *result, int *used) {
  /* your code here */
}

int main() {
  /* create arrays */
  /* read n */
  /* call permut once */
  return 0;
}

Can you calculate how many permutations do you get for the given n?

Answer: n! (n factorial) .