How to generate permutations of an array or string

I've been asked this on interviews a number of times, so I think it counts as "common questions". The answer is simple.

It can be done recursively in a logical way: having a function which takes an array, swap the first element with all the others, in turn, and at each turn, call the function again for the rest of the array (skipping the first position):

   1:  //head is the original array, unchanged between functions calls

   2:  //this is so that we can print the full array

   3:  //first is the "partial" array, which is being permuted now

   4:  void permutations(int* head, int totalLen, int* first, int len) {

   5:      if (len == 1) {//we reached the end of the array

   6:          for (int i = 0; i < totalLen; i++)

   7:              cout << head[i] << " ";

   8:          cout << endl;

   9:          return;

  10:      }

  11:      //first do all the permutations

  12:      //without swaping the first element with all the others

  13:      permutations(head, totalLen, first + 1, len - 1);

  14:      int temp = first[0];

  15:      for (int i = 1; i < len; i++) {

  16:          first[0] = first[i]; //swap the first element

  17:          first[i] = temp; //with all the others, in turn

  18:          permutations(head, totalLen, first + 1, len - 1);

  19:          first[i] = first[0]; //each turn generate permutations for

  20:          first[0] = temp;// the rest of the array, then swap back the first elem

  21:      }

  22:  }

The function is called like this:

   1:      int size = 4;

   2:      int vec[] = { 1, 2, 3, 4 };

   3:      permutations(vec, size, vec, size);