Heap'in algoritması n nesnenin tüm permütasyonlarını oluşturmak için kullanılır. Buradaki fikir, bir önceki permütasyondan her bir permütasyonu, diğerini rahatsız etmeden değiştirilecek bir çift öğe seçerek oluşturmaktır. n-2 unsurlar.
Aşağıda verilen n sayıdaki tüm permütasyonların nasıl oluşturulduğu gösterilmiştir.
Örnek:
Input: 1 2 3 Output: 1 2 3 2 1 3 3 1 2 1 3 2 2 3 1 3 2 1
Algoritma:
- Algoritma şunu üretir: (n-1)! bunların her birine son elemana bitişik olan ilk n-1 elemanın permütasyonları. Bu, son öğeyle biten tüm permütasyonları üretecektir.
- Eğer n tek ise ilk ve son elemanı değiştirin, eğer n çift ise i'yi değiştirinbuöğesini (i, 0'dan başlayan sayaçtır) ve son öğeyi seçin ve yukarıdaki algoritmayı i, n'den küçük olana kadar tekrarlayın.
- Her yinelemede algoritma, geçerli son öğeyle biten tüm permütasyonları üretecektir.
Uygulama:
C++// C++ program to print all permutations using // Heap's algorithm #include
// Java program to print all permutations using // Heap's algorithm import java.io.*; 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.
# 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# 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*/
<script> // JavaScript program to print all permutations using // Heap's algorithm // Prints the array function printArr(an) { document.write(a.join(' ')+'
'); } // Generating permutation using Heap Algorithm function heapPermutation(asizen) { // 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>
Çıkış
1 2 3 2 1 3 3 1 2 1 3 2 2 3 1 3 2 1
Zaman Karmaşıklığı: O(N*N!) Burada N, verilen dizinin boyutudur.
Yardımcı Alan: N boyutunda özyinelemeli yığın alanı için O(N).
Referanslar:
1. 'https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3