0131. Permutations

Input file name:	perm.in
Output file name:	perm.out
Time limit:	500 ms
Memory limit:	64 megabytes

Generate all permutations of numbers 1,…,n in such an order that any two adjacent permutations differ only by the order of two adjacent elements (that is, 1, 2, 3, 4 can be followed by 1, 2, 4, 3, but not by 1, 4, 3, 2).

Input file

Input file contains an integer number 1 ≤ n ≤ 8.

Output file

Output file should contain n! lines, n numbers each (separated by spaces).

Examples:

perm.in	perm.out
3	1 2 3 1 3 2 3 1 2 3 2 1 2 3 1 2 1 3

Source: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version