Necesito generar todas las combinaciones posibles de N parámetros. ¿Hay una forma más rápida (más eficiente) de hacerlo que incrustar N para bucles?

Answer 1

Si N es grande, anidar tantos bucles daría como resultado un código horrible. Si N es variable, tener tantas capas anidadas sería completamente imposible en la mayoría de los idiomas.

Una alternativa sería tener un solo ciclo que se ejecute de 0 a 10 ^ N – 1; los dígitos del contador de bucle en la base 10 se correlacionarían con los parámetros. Sin embargo, extraer esos dígitos implicaría mucha aritmética adicional. En cambio, podría tener una matriz de longitud N que almacene los parámetros. El primero se incrementaría en cada iteración, módulo 10. Cada vez que un parámetro pasa a 0, el siguiente tendría que incrementarse. Agregar esa lógica de ramificación también incurriría en una penalización de rendimiento.

(Vaya, acabo de notar que los parámetros tendrían hasta 10 valores, no exactamente 10. Si el rango es el mismo para todos los parámetros, lo anterior podría adaptarse fácilmente; de ​​lo contrario, sería aún más incómodo. Pero no se preocupe, la conclusión a continuación sigue en pie 😉

Por lo tanto, también podría optar por la implementación recursiva equivalente. Elimina esas ramas y mejora la legibilidad, pero agrega sobrecarga de llamadas a funciones. La torpe alternativa iterativa probablemente solo sería ventajosa si N puede crecer tanto que los desbordamientos de la pila sean una preocupación.

Teniendo en cuenta estas cosas, podemos ver que si bien anidar N bucles podría no ser el código más bonito, en el caso general no se puede superar en términos de velocidad.

(Para un problema más concreto, podría haber oportunidades para obtener ganancias de rendimiento a través de técnicas como paralelización, bloqueo de bucles, etc.)

Answer 2

En esta pregunta, puede ver que el patrón tiene elementos de un determinado conjunto. Entonces, en lugar de usar n bucles, simplemente puede usar la recursión con una variable de contador.

// se verá como

void myfun (int n, int i, int a [], int arr [], int size)
{
si (i == n) {
para (int j = 0; j cout << a [j] << "";
}
cout << endl;
regreso;
}

para (int j = 0; j a [i] = arr [j];
myfun (n, i + 1, a, arr, tamaño);
}
}

Espero que esto te aclare la duda. feliz codificación .. 🙂

Answer 3

Mi primera inclinación sería alcanzar R, donde esta es una línea.

> combn (1: 5, 3)
[, 1] [, 2] [, 3] [, 4] [, 5] [, 6] [, 7] [, 8] [, 9] [, 10]
[1,] 1 1 1 1 1 1 2 2 2 3
[2,] 2 2 2 3 3 4 3 3 4 4
[3,] 3 4 5 4 5 5 4 5 5 5

Mi segunda respuesta es: ¿cuánto más rápido será la solución óptima y cuánto tiempo ha pasado tratando de encontrar una solución óptima? A menos que esto sea un cuello de botella en el rendimiento, busque la solución estúpida y obvia y continúe con problemas más sustanciales.

Answer 4

Una colección de todas las combinaciones posibles de algunos objetos se denomina conjunto de potencia. Aquí hay un algoritmo para generarlos: un generador de powerset en python

Answer 5

Hay dos algoritmos ampliamente utilizados para esto:

Algoritmo del montón

Algoritmo Steinhaus – Johnson – Trotter