Ejemplo de un algoritmo de tiempo factorial O (n!)

Solución:

Genera todas las permutaciones de una lista.

Tú tienes n! listas, por lo que no puede lograr una mejor eficiencia que O(n!).

El vendedor ambulante tiene una solución ingenua que es O (n!), Pero tiene una solución de programación dinámica que es O (n ^ 2 * 2 ^ n)

Listar todas las permutaciones de una matriz es O (n!). A continuación se muestra una implementación recursiva utilizando el método de intercambio. La recursividad está dentro del bucle for y los elementos de la matriz se intercambian en posición hasta que no quedan más elementos. Como puede ver en el recuento de resultados, el número de elementos en la matriz es n !. Cada permutación es una operación y hay n! operaciones.

def permutation(array, start, result)
    if (start == array.length) then
        result << array.dup  
    end
    for i in start..array.length-1 do
        array[start], array[i] = array[i], array[start]
        permutation(array, start+1,result)
        array[start], array[i] = array[i], array[start]
    end 
    result   
end        


p permutation([1,2,3], 0, []).count  #> 6 = 3!
p permutation([1,2,3,4], 0, []).count #> 24 = 4!
p permutation([1,2,3,4,5], 0, []).count #> 120 = 5!

---

---

Utiliza Nuestro Buscador