Shulou(Shulou.com)05/31 Report--

Today, the editor will share with you the relevant knowledge points about how to use the recursive exchange method in the full arrangement of C++. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

Topic description

Output natural numbers 1 to n all non-repetitive permutations, that is, the full permutations of n, require that duplicate numbers are not allowed in any sequence of numbers generated.

Input format

An integer n.

Output format

All non-repeating sequences of numbers consisting of 1n, one sequence per line.

Each number retains 5 field widths.

Input exampl

three

Output sample

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

Full permutation problem-- Recursive Exchange method

In fact, the idea is similar to the idea of violence enumeration. what is the x number of each recursive enumeration, and then a [x] can choose not to move, or you can choose to exchange position with any one of the following numbers, that is, choose a number from behind and put it on the position of x.

In short, it is difficult to understand that each person chooses an unused number to exchange with that digit, so you can push the example according to the program.

So we can print all the permutations, but this is not in order, so we need to sort a [x] ~ a [n] every time.

For example, make a full arrangement of 1, 2, and 3. When we exchange 1 and 3, the sequence becomes 3, 2, 1, if there is no sorting here, direct 2, 1 remain unchanged, we will output 3, 2, 1, but what we want first should be 3, 1, 2, so we have to sort.

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

Code

# include # include # include # include using namespace std;const int N_MAX = 10 political int ntert int a [N _ MAX + 10]; void permutation (int x) {if (x = = n) {for (int I = 1; I)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.