2169. Permutations

Given a positive integer n, print all permutations of integers from 1 to n in lexicographical order.

Input. One positive integer n (1 ≤ n ≤ 8).

Output. Print all permutations of integers from 1 to n in lexicographical order. Print each permutation on a separate line.

Sample input	Sample output
3	1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

SOLUTION

combinatorics - permutations

Algorithm analysis

In this problem you must generate all permutations of numbers from 1 to n. This can be done, for example, using the next_permutation function.

Algorithm implementation

Use the array m to generate the permutations.

int m[10];

Read the input value of n.

scanf("%d",&n);

Initialize the array m with the initial permutation 1 2 3…. n, starting from the first index.

for (i = 1; i <= n; i++)

m[i] = i;

Using the next_permutation function, generate all permutations – from the lexicographically smallest to the lexicographically largest.

do

{

Print each generated permutation on a separate line.

for (i = 1; i <= n; i++)

printf("%d ",m[i]);

printf("\n");

} while(next_permutation(m + 1, m + n + 1));

Algorithm implementation – vector

Use the vector v to generate the permutations.

vector<int> v;

Read the input value of n.

scanf("%d", &n);

Initialize the array v with the initial permutation 1 2 3…. n, starting from the zero index.

v.resize(n);

for (i = 0; i < n; i++)

v[i] = i + 1;

Using the next_permutation function, generate all permutations – from the lexicographically smallest to the lexicographically largest.

do

{

Print each generated permutation on a separate line.

for (i = 0; i < n; i++)

printf("%d ", v[i]);

printf("\n");

} while (next_permutation(v.begin(), v.end()));