Algorithm arrangement algorithm and combination algorithm

1.   preface

This paper introduces the commonly used permutation and combination algorithms, including full permutation algorithm, full permutation algorithm, n combination algorithm for m number selection, etc.

2.   Alignment algorithm

Common ranking algorithms are:
(A) lexicographical ordering
(B) incremental carry number method
(C) descending carry number method
(D) ortho substitution
(E) a recursive method

Introduce two commonly used:

(1)   Dictionary sequence method

A sequence relation is specified for the characters in a given character set, from which each permutation is produced in sequence.

With the character set {1,2,3}, the smaller Numbers come first, so that the full order generated in lexicographical order is :123,132,213,231,312,321.

Generating the next permutation for a given full permutation the next permutation of one is the string that has no dictionary order adjacent to the next. This requires that this one and the next have as long a common prefix as possible, i.e. the variation is limited to the shortest possible suffix.

Algorithm idea:

Let P be a full permutation of [1,n].
P = P1P2... Pn = P1P2... PJPJ Pj - 1 + 1... PKPK Pk - 1 + 1... Pn, j = Max {I | Pi < Pi + 1}, {k = Max I | Pi > Pj}, Pj, Pk, Pj+1... PJPK Pk - 1 + 1... Pn flipped, P'= P1P2... Pj - 1 PKPN... Pk + 1 PJPK - 1... Pj plus 1 is the next P

Example: the next permutation of 839647521.

Starting at the far right, find the first number that is smaller than 4(because 4) < 7, and 7 > 5 > 2 > 1), starting at the far right, find the number 5 to the right of 4, which is greater than 4 > 2 > 1 and 4 < 5), swap 4 and 5, then the right side of 5 is 7421, and the upside down is 1247, so the next permutation is 839651247. The non-recursive algorithm for the whole permutation is written as follows

This method supports data duplication and is adopted in the C++ STL.

(2)   The recursive method

Set p = {r1, r2, r3... Rn}, perm(p), pn = p,rn}. Then perm(p) = r1perm(p1), r2perm(p2), r3perm(p3)... , rnperm (pn). When n = 1, perm of p} = r1.

For example: find the full array of {1, 2, 3, 4, 5}

1. First look at the last two Numbers, 4 and 5. They have a total permutation of 4, 5, and 5, 4, which is the total permutation of 5 starting with 4 and the total permutation of 4 starting with 5.

Since the whole arrangement of a number is itself, we get the above result.

2. Look at the last three Numbers: 3, 4, 5. The full order of them is 3, 4, 5, 3, 5, 4, 3, 5, 4, 5, 4, 5, 5, 3, 5, 3, 5, 4, 4, 3.

It's a combination of all permutations starting with 3 and 4 and 5, all permutations starting with 4 and 3 and 5 and all permutations starting with 5 and 3 and 4.

#include <stdio.h>
 
int n = 0;
 
void swap(int *a, int *b)
 
{
 
 int m;
 
 m = *a;
 
 *a = *b;
 
 *b = m;
 
}
 
void perm(int list[], int k, int m)
 
{
 
 int i;
 
 if(k > m)
 
 {
 
  for(i = 0; i <= m; i++)
 
   printf("%d ", list[i]);
 
  printf("n");
 
  n++;
 
 }
 
 else
 
 {
 
  for(i = k; i <= m; i++)
 
  {
 
   swap(&list[k], &list[i]);
 
   perm(list, k + 1, m);
 
   swap(&list[k], &list[i]);
 
  }
 
 }
 
}
 
int main()
 
{
 
 int list[] = {1, 2, 3, 4, 5};
 
 perm(list, 0, 4);
 
 printf("total:%dn", n);
 
 return 0;
 
}

3.   Combination algorithm

3.1   All combination

The binary conversion method is introduced here, that is, each combination corresponds to a binary number, while enumerating the binary, enumerating each combination. Such as string: abcde

00000 < �   � > null
00001< �   � > e
00010 < �   � > d
 ...   ... 
11111 < �   � > abcde

3.2   N choose m

(1)   recursive

A. First select the number with the largest number from n number, and then select m-1 number from the remaining n-1 number, until select 1 number from n-(m-1) number.

B. Select a number with a lower number from n and continue with step 1 until the largest number of the current optional number is m.

The following is the implementation of the recursive method:

//Find all the combinations of any m elements from the array a[1..n].
 
/// a[1..n] represents the candidate set, n is the size of the candidate set, n> = m> 0.
 
/// b[1..M] is used to store the elements in the current combination (in this case, the element subscripts),
 
/// constant M represents the number of elements in a combination that satisfies the condition, M= M, and these two parameters are only used to output the result.
 
void combine( int a[], int n, int m, int b[], const int M )
 
{
 
 for(int i=n; i>=m; i--)  //Notice the scope of the loop here
 
 {
 
  b[m-1] = i - 1;
 
  if (m > 1)
 
   combine(a,i-1,m-1,b,M);
 
  else           //M == 1, output a combination
 
  {
 
   for(int j=M-1; j>=0; j--)
 
   cout << a[b[j]] << " ";
 
   cout << endl;
 
  }
 
 }
 
}

(2)   01 transformation method

The idea of this program is to open an array, its subscript represents 1 to n Numbers, the value of the array element is 1 means that the number it represents is selected, is 0 is not selected.

First, initialize the first n elements of the array to 1, indicating that the first combination is the first n elements.

Then scan the "10" combination of array element values from left to right, find the first "10" combination and change it to "01", while moving all the "1" to the left of the array.

When the first "1" is moved to the n-m position of the array, that is, all n "ones" are moved to the rightmost end, the last combination is obtained.

For example, find a combination of 5 choose 3:

1 1 1 0 0 //1,2,3
 
1 1 0 1 0 //1,2,4
 
1 0 1 1 0 //1,3,4
 
0 1 1 1 0 //2,3,4
 
1 1 0 0 1 //1,2,5
 
1 0 1 0 1 //1,3,5
 
0 1 1 0 1 //2,3,5
 
1 0 0 1 1 //1,4,5
 
0 1 0 1 1 //2,4,5
 
0 0 1 1 1 //3,4,5

4.   The resources
(1)   / / www.jb51.net/article/54441.htm
(2)   / / www.jb51.net/article/54443.htm
(3)   Combination algorithm

The idea of this program is to open an array, its index represents the number from 1 to m, the value of the array element is 1 means that the index represents the number is selected, is 0 is not selected.

First, initialize the first n elements of the array to 1, indicating that the first combination is the first n elements.

Then scan the "10" combination of array element values from left to right, find the first "10" combination and change it to "01", while moving all the "1" to the left of the array.

When the first "1" is moved to the m-n position of the array, that is, the n "ones" are all moved to the rightmost end, the last combination is reached.

For example, find a combination of 5 choose 3:
1, 1, 1, 0, 0 //1,2,3
1, 1, 0, 1, 0 //1,2,4
1, 0, 1, 1, 0 //1,3,4
0, 1, 1, 0 over //2,3,4
1, 1, 0, 0, 1 over /1,2,5
1, 0, 1, 0, 1 over /1,3,5
0, 1, 1, 0, 1 over /2,3,5
1, 0, 0, 1, 1 over /1,4,5
0, 1, 0, 1, 1 over /2,4,5
0, 0, 1, 1, 1 over 3,4,5