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);`

Recursive is stress stack limit; try non-recursive one;

ReplyDeleteyou're welcome to contribute with a better solution :)

ReplyDeletewhat is your idea for a iterative solution?

ReplyDelete