# Heap’s algorithm for Permutations

By | April 25, 2016

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 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]", ""));
} 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);
}
```
1. khiemtr Post author

Sound good! Thanks Nhan very much for your solution.

This site uses Akismet to reduce spam. Learn how your comment data is processed.