In most cases, enumeration problems are solved by recursive enumeration. Unfortunately, there is no general approach, because often, iteration methods are highly dependent on the task itself.
However, one can notice some similarity among the methods of enumeration of various combinatorial objects. Therefore, for an illustrative example, consider a code that generates all combinations from n to k.
int n, k;
// An array that supports combination prefixes.
//
// The prefix in this case means that we have selected some objects in the combination.
//
// Subsequently, they will either be completed in the correct combination,
// or the recursion will cut off the branch when it realizes that such a prefix cannot be completed correctly
vector arr;
// the recursive iteration function itself
//
// pos - number of the object in combination, which we will determine at the current moment (from 0 to k - 1)
//
// prev - the value of the object that was taken in the previous step
//
// In combinations, the order of objects is not important ([1, 2] and [2, 1] are considered the same and similar),
// so we only want to generate sets where the object values are in ascending order.
//
// This is necessary so that the same options such as [1, 2] and [2, 1] are iterated only once
// (in our case, we'll only consider [1, 2], but not [2, 1] since it's not an ordered set).
//
// That's why we keep the prev variable to reduce the number of iterations
void rec(int pos, int prev) {
// if the number of the selected element is equal to k, then we have already selected all elements
// because their numbers are from 0 to k - 1
if (pos == k) {
// if the condition is met, then the correct combination is now in the arr array
// and we can process it somehow (in this case, just print it to the console)
for (int i = 0; i < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
return; // cut off the recursion branch, because already got a combination and no need to continue further
}
// here we check if we can get the correct combination from the remaining elements
// if there are not enough remaining elements, then we cut off this recursion branch
if (k - pos > n - prev - 1)
return;
// iterate over the object that we put on the position with index pos
// but because we want an ordered set, then the minimum possible value is prev + 1
for (int i = prev + 1; i < n; i++) {
arr.push_back(i); // Add an element to the global array. Now we seem to have chosen him
rec(pos + 1, i); // run recursively to set the following items
arr.pop_back(); // after returning from the recursion, our currently selected element is no longer relevant,
// because inside the recursion, we went through all the options with such a prefix,
// so this element needs to be removed
}
}
int main()
{
cin>> n>> k;
// initially we will set the element at the 0th position
// we assume that the element -1 was selected before, so that the iteration initially starts from a null object
rec(0, -1);
return 0;
}
The same code, but without comments:
int n, k;
vector arr;
void rec(int pos, int prev) {
if (pos == k) {
for (int i = 0; i < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
return;
}
if (k - pos > n - prev - 1)
return;
for (int i = prev + 1; i < n; i++) {
arr.push_back(i);
rec(pos + 1, i);
arr.pop_back();
}
}
int main() {
cin>> n>> k;
rec(0, -1);
return 0;
}
In recursive iterations, special attention should always be paid to recursion cuts. In practice, they can greatly speed up the program.
|