Lexicographic order -- full arrangement in bell sound

Write an algorithm to solve the problem of bell ringing by computer

It is known that there is 12 Oral chime , Knock randomly , So how many full permutations are there ？

We found that , You can add a shorter permutation to a highest order and move it to grow an element permutation .

So we think of recursion .

So how to arrange them all by computer ？

The dictionary order is adopted here .

 

 

 

Here we can find , According to the dictionary order , The last permutation should be 321, Scan from right to left , The number on the left should be strictly greater than that on the right .

 

1.

 

 2. here 1 Than 3 Small , Therefore, the ratio suffix should be used ( The sequence after the descent point ） in 1 The smallest number of large , namely 2 And 1 swapping , At this time, the suffix is 31, Not the minimum suffix , therefore 31 Exchange for 213, And so on and so on , That is, you can get all the permutations .

 

sjt Algorithm

Define a new concept ： Movable number

 

 1. Point all numbers in the spread to the left .

2. The maximum movable number is successively exchanged with the adjacent number on the left until the end point , At the same time, one by one permutation is generated .

3. At this time, the maximum number cannot be moved , At this time, the maximum movable number is exchanged with the number of neighbors pointing to the direction , Then the direction of all the movable numbers is reversed .

4. At this time, the maximum movable number is transposed with the number pointing to the direction ...

...... You can get all the sequences by cycling .

Function implementation and call mode