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.
- Final all possible Permutations from the array. So possible permutation is n! = 3! = 6 cases.
- 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:
- Heap, “Permutations by interchanges,” Computer Journal, 1963.
- Knuth, The Art of Computer Programming, vol.4sec.7.2.1.1
Accessed at www-cs-faculty.stanford.edu/~knuth/taocp.html - Ord-Smith , “Generation of permutation sequences,” Computer Journal, 1970-71
- Sedgewick, Permutation Generation Methods, Computing Surveys, 1977. Note Accessed http://www.cs.princeton.edu/~rs/talks/perms.pdf
- Trotter, “Perm (Algorithm 115 ),” CACM,1962
- Wells , Elements of combinatorial computing, 1961
- Decrease and Conquer for Permutations, Design and Analysis of Algorithms. Accessed http://www.cs.uni.edu/~wallingf/teaching/cs3530/sessions/session15.html#pilgrim
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); }Sound good! Thanks Nhan very much for your solution.