El algoritmo de Heap se usa para generar todas las permutaciones de n objetos. La idea es generar cada permutación a partir de la permutación anterior eligiendo un par de elementos para intercambiar, sin perturbar a los otros n-2 elementos.
A continuación se muestra la ilustración de la generación de todas las permutaciones de n números dados.
Ejemplo:
Input: 1 2 3
Output: 1 2 3
2 1 3
3 1 2
1 3 2
2 3 1
3 2 1
Algoritmo:
- ¡El algoritmo genera (n-1)! permutaciones de los primeros n-1 elementos, adjuntando el último elemento a cada uno de estos. Esto generará todas las permutaciones que terminen con el último elemento.
- Si n es impar, intercambie el primer y último elemento y si n es par, luego intercambie el i -ésimo elemento (i es el contador que comienza desde 0) y el último elemento y repita el algoritmo anterior hasta que i sea menor que n.
- En cada iteración, el algoritmo producirá todas las permutaciones que terminen con el último elemento actual.
Implementación:
C++
// C++ program to print all permutations using
// Heap's algorithm
#include <bits/stdc++.h>
using namespace std;
// Prints the array
void printArr(int a[], int n)
{
for (int i = 0; i < n; i++)
cout << a[i] << " ";
printf("\n");
}
// Generating permutation using Heap Algorithm
void heapPermutation(int a[], int size, int n)
{
// if size becomes 1 then prints the obtained
// permutation
if (size == 1) {
printArr(a, n);
return;
}
for (int i = 0; i < size; i++) {
heapPermutation(a, size - 1, n);
// if size is odd, swap 0th i.e (first) and
// (size-1)th i.e (last) element
if (size % 2 == 1)
swap(a[0], a[size - 1]);
// If size is even, swap ith and
// (size-1)th i.e (last) element
else
swap(a[i], a[size - 1]);
}
}
// Driver code
int main()
{
int a[] = { 1, 2, 3 };
int n = sizeof a / sizeof a[0];
heapPermutation(a, n, n);
return 0;
}
Java
// Java program to print all permutations using
// Heap's algorithm
class HeapAlgo {
// Prints the array
void printArr(int a[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(a[i] + " ");
System.out.println();
}
// Generating permutation using Heap Algorithm
void heapPermutation(int a[], int size, int n)
{
// if size becomes 1 then prints the obtained
// permutation
if (size == 1)
printArr(a, n);
for (int i = 0; i < size; i++) {
heapPermutation(a, size - 1, n);
// if size is odd, swap 0th i.e (first) and
// (size-1)th i.e (last) element
if (size % 2 == 1) {
int temp = a[0];
a[0] = a[size - 1];
a[size - 1] = temp;
}
// If size is even, swap ith
// and (size-1)th i.e last element
else {
int temp = a[i];
a[i] = a[size - 1];
a[size - 1] = temp;
}
}
}
// Driver code
public static void main(String args[])
{
HeapAlgo obj = new HeapAlgo();
int a[] = { 1, 2, 3 };
obj.heapPermutation(a, a.length, a.length);
}
}
// This code has been contributed by Amit Khandelwal.
Python3
# Python program to print all permutations using # Heap's algorithm # Generating permutation using Heap Algorithm def heapPermutation(a, size): # if size becomes 1 then prints the obtained # permutation if size == 1: print(a) return for i in range(size): heapPermutation(a, size-1) # if size is odd, swap 0th i.e (first) # and (size-1)th i.e (last) element # else If size is even, swap ith # and (size-1)th i.e (last) element if size & 1: a[0], a[size-1] = a[size-1], a[0] else: a[i], a[size-1] = a[size-1], a[i] # Driver code a = [1, 2, 3] n = len(a) heapPermutation(a, n) # This code is contributed by ankush_953 # This code was cleaned up to by more pythonic by glubs9
C#
// C# program to print all permutations using
// Heap's algorithm
using System;
public class GFG {
// Prints the array
static void printArr(int[] a, int n)
{
for (int i = 0; i < n; i++)
Console.Write(a[i] + " ");
Console.WriteLine();
}
// Generating permutation using Heap Algorithm
static void heapPermutation(int[] a, int size, int n)
{
// if size becomes 1 then prints the obtained
// permutation
if (size == 1)
printArr(a, n);
for (int i = 0; i < size; i++) {
heapPermutation(a, size - 1, n);
// if size is odd, swap 0th i.e (first) and
// (size-1)th i.e (last) element
if (size % 2 == 1) {
int temp = a[0];
a[0] = a[size - 1];
a[size - 1] = temp;
}
// If size is even, swap ith and
// (size-1)th i.e (last) element
else {
int temp = a[i];
a[i] = a[size - 1];
a[size - 1] = temp;
}
}
}
// Driver code
public static void Main()
{
int[] a = { 1, 2, 3 };
heapPermutation(a, a.Length, a.Length);
}
}
/* This Java code is contributed by 29AjayKumar*/
Javascript
<script>
// JavaScript program to print all permutations using
// Heap's algorithm
// Prints the array
function printArr(a,n)
{
document.write(a.join(" ")+"<br>");
}
// Generating permutation using Heap Algorithm
function heapPermutation(a,size,n)
{
// if size becomes 1 then prints the obtained
// permutation
if (size == 1)
printArr(a, n);
for (let i = 0; i < size; i++) {
heapPermutation(a, size - 1, n);
// if size is odd, swap 0th i.e (first) and
// (size-1)th i.e (last) element
if (size % 2 == 1) {
let temp = a[0];
a[0] = a[size - 1];
a[size - 1] = temp;
}
// If size is even, swap ith
// and (size-1)th i.e last element
else {
let temp = a[i];
a[i] = a[size - 1];
a[size - 1] = temp;
}
}
}
// Driver code
let a=[1, 2, 3];
heapPermutation(a, a.length, a.length);
// This code is contributed by rag2127
</script>
Producción:
1 2 3 2 1 3 3 1 2 1 3 2 2 3 1 3 2 1
Referencias:
1. “https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
Este artículo es una contribución de Rahul Agrawal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando escribir .geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA