El Algoritmo de Heap genera todas las permutaciones posibles de N objetos. Fue propuesto por primera vez por B. R. Heap En 1963.[1] El algoritmo minimiza movimiento: genera cada permutación de la anterior intercambiando un par de elementos; los otros N−2 elementos no se alteran. En una revisión de 1977 de algoritmos generadores de permutación, Robert Sedgewick concluyó que sea en aquel tiempo el algoritmo más eficaz para generar permutaciones por computadora.[2]
Un mapa de las 24 permutaciones y los 23 intercambios utilizados en Algoritmo de Heap permuting las cuatro letras A (ámbar), B (azul), C (ciánico) y D (rojo oscuro)
Detalles del algoritmo
Supongamos que tenemos una permutación que contiene N elementos diferentes. Heap encontró un método sistemático para escoger en cada paso un par de elementos para cambiar, para producir cada permutación posible de estos elementos exactamente una vez. Describamos el método de Heap de una manera recursiva. Primero pusimos un contador i a 0. Realizamos los siguientes pasos repetidamente hasta que i es igual a N. Utilizamos el algoritmo para generar el (N − 1)! permutaciones de los primeros N − 1 elementos, contiguos el último elemento a cada cual de estos. Esto genera todas las permutaciones que terminan con el último elemento. Entonces siN es impar, cambiamos el primero elemento y el último, mientras que si N es par podemos cambiar el i-ésimo elemento y el último (no hay ninguna diferencia entre N par e impar en la primera iteración). Añadimos uno al contador i y repetimos. En cada iteración, el algoritmo producirá todas las permutaciones que terminan con el elemento que acaba de ser movido a la "última" posición. El siguiente pseudocode genera todas las permutaciones de una matriz de datos de longitud N.
Sedgewick, Robert. «a talk on Permutation Generation Algorithms».
Datos:Q16907296
Agosto 24, 2021
algoritmo, heap, genera, todas, permutaciones, posibles, objetos, propuesto, primera, heap, 1963, algoritmo, minimiza, movimiento, genera, cada, permutación, anterior, intercambiando, elementos, otros, elementos, alteran, revisión, 1977, algoritmos, generadore. El Algoritmo de Heap genera todas las permutaciones posibles de N objetos Fue propuesto por primera vez por B R Heap En 1963 1 El algoritmo minimiza movimiento genera cada permutacion de la anterior intercambiando un par de elementos los otros N 2 elementos no se alteran En una revision de 1977 de algoritmos generadores de permutacion Robert Sedgewick concluyo que sea en aquel tiempo el algoritmo mas eficaz para generar permutaciones por computadora 2 Un mapa de las 24 permutaciones y los 23 intercambios utilizados en Algoritmo de Heap permuting las cuatro letras A ambar B azul C cianico y D rojo oscuro Detalles del algoritmo EditarSupongamos que tenemos una permutacion que contiene N elementos diferentes Heap encontro un metodo sistematico para escoger en cada paso un par de elementos para cambiar para producir cada permutacion posible de estos elementos exactamente una vez Describamos el metodo de Heap de una manera recursiva Primero pusimos un contador i a 0 Realizamos los siguientes pasos repetidamente hasta que i es igual a N Utilizamos el algoritmo para generar el N 1 permutaciones de los primeros N 1 elementos contiguos el ultimo elemento a cada cual de estos Esto genera todas las permutaciones que terminan con el ultimo elemento Entonces si N es impar cambiamos el primero elemento y el ultimo mientras que si N es par podemos cambiar el i esimo elemento y el ultimo no hay ninguna diferencia entre N par e impar en la primera iteracion Anadimos uno al contador i y repetimos En cada iteracion el algoritmo producira todas las permutaciones que terminan con el elemento que acaba de ser movido a la ultima posicion El siguiente pseudocode genera todas las permutaciones de una matriz de datos de longitud N procedure generate n integer A array of any if n 1 then output A else for i 0 i lt n i 1 do generate n 1 A if n is even then swap A i A n 1 else swap A 0 A n 1 end if end for end if Tambien se puede escribir el algoritmo en un formato no recursivo 3 procedure generate n integer A array of any c array of int for i 0 i lt n i 1 do c i 0 end for output A i 0 while i lt n do if c i lt i then if i is even then swap A 0 A i else swap A c i A i end if output A c i 1 i 0 else c i 0 i 1 end if end whileVe tambien EditarSteinhaus Johnson Trotter algorithmReferencias Editar Permutations by Interchanges The Computer Journal 6 3 293 4 1963 doi 10 1093 comjnl 6 3 293 Sedgewick R 1977 Permutation Generation Methods ACM Computing Surveys 9 2 137 164 doi 10 1145 356689 356692 Sedgewick Robert a talk on Permutation Generation Algorithms Datos Q16907296Obtenido de https es wikipedia org w index php title Algoritmo de Heap amp oldid 135017045, wikipedia, wiki, leyendo, leer, libro, biblioteca,
