Examples of recursive switching method in C++ full permutation are explained in detail

There are the most violent recursive enumeration methods for solving full permutation problems, but we want to optimize the time, so we have recursive interchange.

sample

Los valley 1706

Topic describes

The output of all non-repeated permutations of natural Numbers 1 to n, i.e. the full permutation of n, requires that no repeated Numbers are allowed in any sequence of 1 digits produced.

Input format

1 integer n.

The output format

All non-repeating sequence of Numbers from 1 to n, 1 sequence per line.

Each number retains 5 field widths.

Enter the sample

[

3

]

The output sample

[

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

]

Permutation problem -- Recursive interchange method

In fact, it is similar to the idea of violent enumeration, each recursive enumeration x number is what, then a[x] can choose not to move, or choose to switch with any number after the position, is to choose a number after the position of x.

In short, for every 1 digit, you swap it with an unused number from the end, which is a little confusing, but you can programmatically push the following example.

This allows us to print all the permutation, but not sequentially, so we need to sort a[x] ~ a[n] each time.

Take, for example, a full permutation of 1, 2, and 3. When we swap 1 and 3, the sequence becomes 3, 2, 1, so if we don't sort here, we just keep both 2 and 1, we print 3, 2, 1, but we want 3, 1, 2, so we sort.

Finally, calculate the time complexity of 1, we find that we need to look from 1 to n1 bit, and then enumerate x ~ n, so the total time complexity is O(n!). .

code

# include <cstdio>
# include <cmath>
# include <cstring>
# include <algorithm>

using namespace std;

const int N_MAX = 10;

int n;
int a[N_MAX + 10];

void permutation(int x)
{
 if (x == n) {
  for (int i = 1; i <= n; i++)
   printf("%5d", a[i]);
  printf("\n");
  return;
 }
 for (int i = x; i <= n; i++) {
  sort(a + x, a + n + 1);
  swap(a[x], a[i]);
  permutation(x + 1);
  swap(a[x], a[i]);
 }
}

int main()
{
 scanf("%d", &n);
 for (int i = 1; i <= n; i++)
  a[i] = i;
 permutation(1);
 return 0;
}

Above is this site to you all the relevant knowledge points, thank you for the site's support.