A summary of the full array generation algorithm in Java

  The algorithm of generating full permutation is to enumerate all possible permutations without repetition or omission in an effective way for a given character set. Any arrangement of n character sets can correspond to the arrangement of n Numbers from 1 to n,
  Therefore, this paper takes the permutation of n Numbers as an example to illustrate the permutation generation method.

  There is a definite linear order relation between the total permutation of n characters. All permutations except the last have a successor; Except for the first array, there is a precursor. The successor of each permutation can be obtained from its precursor after a minimum of changes, and the algorithm for the generation of all permutations is the method of generating all permutations one by one from the first permutation.

  The generation method of full array usually has the following:

  Dictionary sequence method
  Progressive decimal system
  Decrement number system
  Ortho exchange method
  Recursive classification algorithm

1. The dictionary order method is efficient and the order is natural

  In lexicographical order, the Numbers 1, 2, 3... The sequence of n is determined by comparing the sequence of corresponding Numbers from left to right. For example, for the arrangement of 12354 and 12345 of 5 Numbers, the arrangement of 12345 comes first, and the arrangement of 12354 comes last. According to this rule, of all the permutations of the five Numbers, the first is 12345 and the last is 54,321.

  The dictionary order algorithm is as follows:

  Let P be a full permutation from 1 to n: P =p1p2... Pn = p1p2... PJPJ pj - 1 + 1... PKPK pk - 1 + 1... The pn
  1) starting from the right end of the array, find the sequence number j of the first number smaller than the right number (j is calculated from the left end), that is, j= Max {I |pi< PI + 1}
  2) in the number to the right of pj, find out the smallest number pk among all the Numbers larger than pj, that is, k= Max {I |pi> Pj} (the number on the right is increasing from right to left, so k is the largest number of all Numbers greater than pj)
  3) swap PI and pk
  4) add pj+1...... Pk -1pkpk+1pn inversion to obtain the permutation p "=p1p2... Pj - 1 PJPN... Pk + 1 PKPK - 1... Pj plus 1, that's the next permutation of p, the next permutation of p.

  For example, 839647521 is a permutation of the Numbers 1 to 9. The steps to generate the next permutation from it are as follows:
  From right to left, find the number 4, 839647521, which is the first number in the array that is smaller than the number on the right
  Find the smallest number greater than 4 in the number after the number 5, 839647521
  You swap 5 with 4 for 839657421
  Reverse 7421 to 839651247
  So the next permutation of 839647521 is 839651247.

2. Progressive decimal system

  In an incrementally carried system of Numbers, the number of mediations is used to find one permutation from another. If you use ki to arrange p1p2... PI... The number of Numbers smaller than PI to the right of the element PI in pn, then the number of permutation mediations is the corresponding permutation k1... Ki... Kn - 1.

  For example, the number of mediations in 839647521 is 72642321,7, 2, 6... The Numbers 8, 3, 9... The number of smaller Numbers on the right-hand side.

  The intermediate number is the intermediate step in calculating the permutation. If you have a permutation, you want the next permutation, and you first determine the number of mediations, the number of mediations after the permutation is the number of mediations in the original permutation plus 1, and it's important to note that if the end of the number of mediations is kn-1+1=2, you carry forward, and in general, if ki+1=n-i+1, you carry forward, and this is the so-called incremental carry system. For example, if the number of mediations for 839647521 is 72642321, the number of mediations for the next array is 67342221+1=67342300 (because 1+1=2, carry forward, 2+1=3, carry again, so the next number is 67342300).

Once you have the number of mediations, you can revert to the deserved order based on it.

  The algorithm is as follows:

  The mediations k1, k2... , the order of the digits of kn-1 represents the digits n, n-1,...... 2. The number of Spaces to the right of the permutation, therefore, k1, k2... , the value of kn-1 from right to left to determine n, n-1,...... , and place one by one in the permutation: I in the ki+1 bit from the right, if someone has put a number, the position is not included, the last space put 1.
 
  So from 67342300 you get the permutation 849617523, which is the last permutation of 839647521. Since 9 is placed first, k1=6, 9 is placed in the 7th place from right, leaving 6 empty Spaces, then 8 is placed, k2=7, 8 is placed in the 8th place from right, but 9 occupies one place, so 8 should be placed in the 9th place from right, and so on.

3. Diminishing carry method

  In the method of incremental carry system, the lowest position of the intermediate number is every 2 into 1, which is frequently carried, which is a disadvantage. If you flip the incremental carry system, you get the decremented carry system.

  The number of mediations in 839647521 is 67342221(k1k2... Kn-1), inverted to 12224376(kn-1... K2k1), which is the number of mediations in the descending carry system: ki(I =n-1,n-2... ,2) carry 1 bit to ki-1 bit at I. Given the permutation p, the number of mediations of the next permutation of p is defined as the number of mediations of p plus 1. For example, p=839647521, the number of mediations of p is 12224376, and the number of mediations of the next permutation of p is 12224376+1=12224377, thus the next permutation of p is 893647521.

  Given the number of mediations, the permutation can be restored in a manner similar to the method of increasing carry Numbers. However, in a descending carry system, the next permutation can be obtained directly from one permutation without first calculating the number of mediations. The specific algorithm is as follows:
  1) if p(I)=n and i< > N, then p(I) is swapped with p(I -1)
  2) if p(n)=n, then find a sequence of continuous decreasing 9, 8... , I, delete it from the left end of the array, and then add it to the right end of the array in reverse order, and then exchange I -1 with the number on the left

  For example, p=893647521 the next permutation is 983647521. When we find the next permutation of 983647521, since 9 is on the far left and the second place is 8, and the third place is not 7, we arrange 8 and 9 from the smallest to the largest to 364752189 on the far right, and then swap 7 with the number to the left to get the next permutation of 983647521 is 367452189. For example, to find the next permutation of 987635421, you only need to rank 9876 from the smallest to the largest to the rightmost end and swap 5 with the number 3 to the left to get 534216789.

4. The ortho-substitution method is the most efficient but the sequence is not natural

  The next permutation in the ortho substitution method is always the result of the substitution of two adjacent permutations in the previous permutation. Take the arrangement of four elements as an example. If the last element 4 is exchanged with the previous element one by one, four new arrangements can be generated:
  1, 2, 3, 4, 1, 2, 4, 3, 1, 4, 2, 3, 4, 1, 2, 3
  Then, the two elements at the end of the last permutation are exchanged, and the four elements at the beginning of the permutation are exchanged successively with the following elements to generate four new permutations:
  4, 1, 3, 2, 1, 4, 3, 2, 1, 3, 4, 2, 1, 3, 2, 1, 3, 2, 4
  Then switch the two elements at the beginning of the last permutation and move the 4 forward:
  Three, one, two, four, three, one, four, two, three, four, one, two, four, three, one, two
  So loop 4 factorial We can find all the permutations.

5. Low efficiency of element increment method (n decimal method)

  1) from the original arrangement p=p1p2...... At the beginning of pn, the NTH bit plus n minus 1, if the value of the bit exceeds n, divide it by n, replace the bit with remainder, and carry (the NTH minus 1 bit plus 1).
  2) treat n-1 bit, n-2 bit in the same way... , until the carry does not occur, a new permutation is produced after processing a permutation
  3) remove the same elements from the list
  4) when the value of the first element > N the end
  Take the arrangement of three Numbers 1, 2, 3: the original arrangement is 1, 2, 3. From there, the third element is 3, 3+2= 5,5 Mod 3=2, and the second element is 2, 2+1=3, so the new arrangement is 1, 3, and 2. By element increment, in sequence
  Arrangement is: 1, 2, 3, 1 2 3 2 1 1, 2, 1, 2, 3, 2, 2, 2, 3 1, 2, 3, 3, 3 1, 2, 3 2 1
  There are repeating elements in the underlined array, discard them, and the rest is the entire array.

6. Recursive classification algorithm

  The generating method of full permutation is simple to describe by recursion.

  1) backtracking method
  Backtracking usually involves constructing a spanning tree. Take three elements for example; The node of the tree has a value of 1, 2, 3. If something is 0, it has not yet been evaluated.
  The initial state is (0,0,0), and the value of the first element can select 1, 2, and 3 respectively, so the three child nodes are extended. The same method is used to find the possible value of the second element of these nodes, and so on and so on. Once the three data of the new node are all non-zero, a full arrangement scheme is found. When all possible solutions are tried, the problem is solved.

  2) recursive algorithm
  If P is used to represent the arrangement of n elements, while Pi is used to represent the arrangement without element I, and (I)Pi is used to represent the arrangement with prefix I before the arrangement of Pi, then the arrangement of n elements can be recursively defined as:
  If n=1, then P has only one element I
  If n> 1, then the permutation P consists of the permutation (I)Pi (I =1, 2... , n - 1).
  By definition, it is easy to see that if the k-1 element arrangement has been generated, then the k element arrangement can be generated by adding element I before each k-1 element arrangement Pi. Such as the arrangement of the two elements are 1, 2 and 1, 2 for and element, p1 is 2, 2, 3 and 3 before each permutation generated 1 plus 1, 2, 3 and 1 2 3 two new arrangement, p2 and p3 is 3, 3, 1 and 2, 2, 1, by the same method can generate the new arrangement 1 2 3, 2, 3, 1 and 3 1 2 1, 2, 3.

  3) cyclic shift method
  If a k-1 permutation has been generated, add element k after each permutation to make it a permutation of k elements, then move each permutation loop to the left (to the right), producing a new permutation each time.
  For example, the arrangement of two elements is 1, 2, and 2, 1. After 1, 2, add 3 to make a new arrangement 1, 2, 3, rotate it to the left and regenerate into a new arrangement 2, 3, 1, 3, 1, 2. Likewise, 2, 1 can generate a new arrangement 2, 1, 3, 1, 3, 2, and 3, 2, 1.

This is the end of the article, I hope you enjoy it.