Description

Given a set of n>=1 elements, the problem is to print all possible permutations of this set.

For example, if n = 3, then the set is (1,2,3), and the set of permutations is

(1,2,3)

(1,3,2)

(2,1,3)

(2,3,1)

(3,2,1)

(3,1,2)

 

• Whenever you want to swap an element, you should swap with the orginal set of the current index.
• For example, the set after (2,3,1) should swap the 1st element, which is to swap with the origin set of current index 1, that is (1,2,3), rather than swap with (2,3,1) itself. And after swap 1 and 3 from (1,2,3), the result is (3,2,1).

 

A recursive method to implement this problem is as follows:

Consider the case of (1,2,3,4), that is, n=4.

1. Place the set elements in a global array, and set the position index “k” as 0.
2. Use a for-loop to “swap” (or exchange) the 1^st element with the 1^st element, the 2^nd element, the 3^rd element, and the 4^th element, respectively.
   • In each loop-iteration:
     1. increment the position index “k” by 1 (for considering only the remaining elements in the following recursive call);
     2. use the updated k to recursively call your permutation function;
     3. note that because you use a global array, remember to swap back the two elements after the iteration.
3. In a recursive-call path, when k reaches n, it means that you get a possible permutation.

Input

An interger n (1=<n<=10) that represents the number of elements in the set.

Output

Print all permutations.

Note that you have to print a '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss