General algorithm and solution of permutation and combination problem realized by C language
- 2020-04-02 02:39:04
- OfStack
Although permutations and combinations are a common problem in life, they are difficult to solve without much thought or experience in programming. Because the permutation problem always takes the permutation first and then the permutation problem is relatively simple, this paper only discusses the realization of the permutation problem in detail. I'm going to pick m of 0 out of n Numbers < m < As an example, the problem can be decomposed into:
1. 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.
2. 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.
Obviously, the above method is a recursive process, that is, the recursive method can be very clean to find all the combinations.
The following is the implementation of the recursive method:
//Find all the combinations of any m elements from the array a[1..n]. < br / >
/// a[1..n] represents the candidate set, n is the size of the candidate set, n> = m> 0. < br / >
/// 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. < br / >
void combine( int a[], int n, int m, int b[], const int M )
{
for(int i=n; i>=m; i--) //Notice the loop range 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;
}
}
}
Because recursive programs can be converted into corresponding non-recursive programs by introducing the stack and backtracking, the combination problem can be solved by backtracking. In order to facilitate our understanding, we can reduce the combinatorial problem to the path traversal problem of the graph, and select all combinations of m Numbers from n Numbers, which is equivalent to finding the path traversal problem from [1,1] to [m,x](m) in a graph like this (illustrated by taking 3 Numbers from 1,2,3,4 as examples) < = x < =n) all paths of position:
1 2 3 4
2 3 4
3 4
Above, intercepting the first m lines of n * n upper right diagonal matrix, if each element of the torque moment as a node in this picture, we ask that all of the portfolio is equivalent to the first line of the first column element [1, 1], a list of arbitrary element to the third line as the end all paths, only nodes between adjacent rows, and the next row of nodes must be in a line of nodes on the right is path connected, all other things being no path is same. Obviously, the sequence of Numbers in either path corresponds to a suitable combination.
The following is the implementation of the non-recursive backtrace method:
//Find all the combinations of any m elements from the array a[1..n]. < br / >
/// a[1..n] represents the candidate set, and m represents the number of elements in a combination. < br / >
/// returns the total number of all combinations. < br / >
int combine(int a[], int n, int m)
{
m = m > n ? n : m;
int* order = new int[m+1];
for(int i=0; i<=m; i++)
order[i] = i-1; //Note here that order[0]=-1 is used as the looping identifier for
int count = 0;
int k = m;
bool flag = true; //Flag finds a valid combination
while(order[0] == -1)
{
if(flag) //Output the desired combination
{
for(i=1; i<=m; i++)
cout << a[order[i]] << " ";
cout << endl;
count++;
flag = false;
}
order[k]++; //Select the new number
at the current location
if(order[k] == n) //Current position is no longer optional, backtrace
{
order[k--] = 0;
continue;
}
if(k < m) //Updates the number of the next position of the current position & NBSP; & have spent & have spent & have spent & have spent & have spent & have spent & have spent & have spent < br / >
{
order[++k] = order[k-1];
continue;
}
if(k == m)
flag = true;
}
delete[] order;
return count;
}
Here is the procedure to test the above functions:
int main()
{
const int N = 4;
const int M = 3;
int a[N];
for(int i=0;i<N;i++)
a[i] = i+1;
//Backtrace method
cout << combine(a,N,3) << endl;
//Recursive method
int b[M];
combine(a,N,M,b,M);
return 0;
}
From the above analysis, it can be seen that there are only two general algorithms to solve combinatorial problems: recursion and backtracking. When it comes to specific problems, recursion is not a good choice for large combinatorial problems because of the restrictions of recursive programs on the number of recursive layers. In this case, only backtracking method can be adopted to solve the problem.
The whole permutation problem of n Numbers is relatively simple, which can be realized by exchanging the positions and enumerating in order. The STL provides next_permutation algorithm for finding the next permutation of a sequence. The algorithm principle is as follows:
1. Starting from the end of the current sequence, look for two adjacent elements, and make the former element * I and the latter element *ii, and satisfy * I
<
* ii;
2. Scan forward again from the end of the current sequence to find the first element greater than * I, and make it *j (j may be equal to ii), and swap elements I and j;
3. Reverse the order of all elements after ii (including ii), so that the resulting arrangement is the next arrangement of the current sequence.
Its implementation code is as follows:
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
if (first == last) return false; //Empty � � < br / >
BidirectionalIterator i = first;
++i;
if (i == last) return false; //There is only one element
i = last; //I points to the tail
--i;
for(;;)
{
BidirectionalIterator ii = i;
--i;
//Above, add the element
if (*i < *ii) //If the previous trick element is less than the next trick element
{
BidirectionalIterator j = last; //Let j point to the tail
while (!(*i < *--j)); //You go from the end to the end until you get something bigger than * I
iter_swap(i, j); //I, j
reverse(ii, last); //All the elements following the stream are rearranged in reverse
return true;
}
if (i == first) //The row goes to the beginning
{
reverse(first, last); //All reverse rearrangement
return false;
}
}
}
The following program demonstrates the use of next_permutation to obtain the full arrangement of a sequence:
int main()
{
int ia[] = {1,2,3,4};
vector<int> iv(ia,ia+sizeof(ia)/sizeof(int));
copy(iv.begin(),iv.end(),ostream_iterator<int>(cout," "));
cout << endl;
while(next_permutation(iv.begin(),iv.end()))
{
copy(iv.begin(),iv.end(),ostream_iterator<int>(cout," "));
cout << endl;
}
return 0;
}
Note: the initial sequence in the above program is arranged from small to large. If the initial sequence is out of order, the program can only find the subsequent sequence from the current sequence, that is, the next_permutation is arranged from small to large.