En la mayoría de los casos, los problemas de enumeración se resuelven mediante enumeración recursiva. Desafortunadamente, no hay un enfoque general, porque a menudo, los métodos de iteración dependen en gran medida de la tarea en sí.
Sin embargo, se puede notar cierta similitud entre los métodos de enumeración de varios objetos combinatorios. Por lo tanto, para un ejemplo ilustrativo, considere un código que genera todas las combinaciones de n a k.
entero n, k;
// Una matriz que admite prefijos combinados.
//
// El prefijo en este caso significa que hemos seleccionado algunos objetos en la combinación.
//
// Posteriormente, se completarán en la combinación correcta,
// o la recursión cortará la rama cuando se dé cuenta de que dicho prefijo no se puede completar correctamente
vectorarr;
// la propia función de iteración recursiva
//
// pos - número del objeto en combinación, que determinaremos en el momento actual (de 0 a k - 1)
//
// anterior - el valor del objeto que se tomó en el paso anterior
//
// En las combinaciones, el orden de los objetos no es importante ([1, 2] y [2, 1] se consideran iguales y similares),
// por lo que solo queremos generar conjuntos donde los valores de los objetos estén en orden ascendente.
//
// Esto es necesario para que las mismas opciones como [1, 2] y [2, 1] se iteren solo una vez
// (en nuestro caso, solo consideraremos [1, 2], pero no [2, 1] ya que no es un conjunto ordenado).
//
// Por eso mantenemos la variable anterior para reducir el número de iteraciones
void rec(int pos, int prev) {
// si el número del elemento seleccionado es igual a k, entonces ya hemos seleccionado todos los elementos
// porque sus números son del 0 al k - 1
si (pos == k) {
// si se cumple la condición, entonces la combinación correcta ahora está en la matriz arr
// y podemos procesarlo de alguna manera (en este caso, simplemente imprímalo en la consola)
para (int i = 0; i < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
devolver; // corta la rama recursiva, porque ya obtuve una combinación y no es necesario continuar
}
// aquí comprobamos si podemos obtener la combinación correcta de los elementos restantes
// si no quedan suficientes elementos, entonces cortamos esta rama recursiva
si (k - pos > n - anterior - 1)
devolver;
// iterar sobre el objeto que ponemos en la posición con índice pos
// pero porque queremos un conjunto ordenado, entonces el valor mínimo posible es prev + 1
para (int i = anterior + 1; i < n; i++) {
arr.push_back(i); // Agrega un elemento a la matriz global. Ahora parece que lo hemos elegido
rec(pos + 1, yo); // ejecutar recursivamente para establecer los siguientes elementos
arr.pop_back(); // después de regresar de la recursividad, nuestro elemento actualmente seleccionado ya no es relevante,
// porque dentro de la recursividad, revisamos todas las opciones con tal prefijo,
// entonces este elemento necesita ser eliminado
}
}
int principal()
{
cin>> n>> k;
// inicialmente estableceremos el elemento en la posición 0
// asumimos que el elemento -1 fue seleccionado antes, por lo que la iteración comienza inicialmente desde un objeto nulo
rec(0, -1);
devolver 0;
}
El mismo código, pero sin comentarios:
entero n, k;
vectorarr;
void rec(int pos, int prev) {
si (pos == k) {
para (int i = 0; i < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
devolver;
}
si (k - pos > n - anterior - 1)
devolver;
para (int i = anterior + 1; i < n; i++) {
arr.push_back(i);
rec(pos + 1, yo);
arr.pop_back();
}
}
int principal() {
cin>> n>> k;
rec(0, -1);
devolver 0;
}
En las iteraciones recursivas, siempre se debe prestar especial atención a los cortes recursivos. En la práctica, pueden acelerar mucho el programa.
|