Permütasyon oluşturmak için Heap Algoritması
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ştirin bu öğ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 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 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.
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 ( ' ' ) + '
' ); } // 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>
Çı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
