Permutation: Heap's algorithm

Posted on | Edited on | Views:

wiki, geeksforgeeks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;

// Java program to print all permutations using 
// Heap's algorithm 
class HeapAlgo {
    void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    // Generating permutation using Heap Algorithm
    void heapPermutation(int[] arr, int n) {
        // if n becomes 1 then prints the obtained permutation
        if (n == 1) {System.out.println(Arrays.toString(arr));return;}

        for (int i = 0; i < n; i++) {
            heapPermutation(arr, n - 1);

            if (n % 2 == 1) { // if n is odd, swap first and last element
                swap(arr, 0, n - 1);
            } else { // If size is even, swap i-th and last element
                swap(arr, i, n - 1);
            }
        }
    }
}

public class MyClass { // Driver // Driver code
    public static void main(String args[]) {
        HeapAlgo obj = new HeapAlgo();
        int[] arr = { 1, 2, 3, 4 };
        obj.heapPermutation(arr, arr.length);
    }
}

0%