Heap’s algorithm for Permutations

By | April 25, 2016 | 95 Views

Problem: Find the biggest number from the array [3, 1, 2] (n = 3). For example: 321 is largest number in comparison with all possible numbers from the array.

Solving: We need to resolve 2 things.

  1. Final all possible Permutations from the array. So possible permutation is n! = 3! = 6 cases.
  2. Find a maximum number from a list of numbers that were combined from the Permutations.

(Moreover, another look, if we sort the array above as decrease order [3, 2, 1] then the largest number should be 321. I think this is not reasonable. For instance, [92, 9, 91] after sorted: [92, 91, 9] but actually 99291 is a maximum instead of 92919 in the order)

The first to find Permutations is really tricky because we need to find an effective algorithm to generate Permutations. In this note, I suggest a candidate – Heap’s algorithm. Actually, there are many other methods to do  such as  Johnson-Steinhaus-Trotter, Sedgewick algorithm, etc…

Original Heap’s algorithm:

ALGORITHM: generate(A, n)
    INPUT    : integer n
             : array A[1..m], where m ≥ n

    if n = 1
       write A
    else
       for i ← 1 to n do
           generate(A, n-1)
           if n is odd
              swap A[1] and A[n]
           else
              swap A[i] and A[n]

Recursive Heap’s algorithm implementation by Java:

public class LargestNumber {
    static List<Integer> permutationNum = new ArrayList<Integer>();

    static public void main(String[] args) {
        int n = 3;
        List<Integer> a = new ArrayList<Integer>(Arrays.asList(3, 1, 2));

        generate(n, a);
        System.out.println(permutationNum);
        System.out.println("Max number is: " +Collections.max(permutationNum));
    }

    /**
     * Heap's algorithm generates all possible permutations of n objects.
     *
     * @param n number of object
     * @param a array list containing all elements need to be permutated.
     */
    public static void generate(int n, List<Integer> a) {
        if (n == 1) {
            // Choose number only then convert to integer
            int number = Integer.valueOf(a.toString().replaceAll("[^0-9]", ""));
            permutationNum.add(number);
        } else {
            for (int i = 0; i < n - 1; i++) {
                generate(n - 1, a);
                if (n % 2 != 0) { //even
                    swap(a, i, n - 1);
                } else {
                    swap(a, 0, n - 1);
                }
            }
            generate(n - 1, a);
        }
    }

    public static <E> void swap(List<E> a, int i, int j) {
        E tmp = a.get(i);
        a.set(i, a.get(j));
        a.set(j, tmp);
    }
}

Output in console:

[312, 132, 231, 321, 312, 132]
Max number is: 321

References:

 

 

2 thoughts on “Heap’s algorithm for Permutations

  1. Nhan

    I have another solution:

    public static void main(String[] args) {
    		List numbers = new ArrayList(Arrays.asList(9, 92, 93));
    		sort(numbers);
    		System.out.println(numbers);
    	}
    
    	private static void sort(List numbers) {
    		for (int i = 0; i < numbers.size() - 1; i++) {
    			for (int j = i + 1; j < numbers.size(); j++) {
    				if (compare(numbers.get(i), numbers.get(j)) < 0) {
    					swap(numbers, i, j);
    				}
    			}
    		}
    		
    	}
    
    	private static void swap(List numbers, int i, int j) {
    		Integer temp = numbers.get(i);
    		numbers.set(i, numbers.get(j));
    		numbers.set(j, temp);
    		
    	}
    
    	private static int compare(Integer integer, Integer integer2) {
    		String first = String.valueOf(integer);
    		String second = String.valueOf(integer2);
    		return Integer.valueOf(first + second) - Integer.valueOf(second + first);
    	}
    
    Reply
    1. khiemtr Post author

      Sound good! Thanks Nhan very much for your solution.

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *