Find all Concatenate Numbers - Sorted

In previous post, the returned results are unsorted, what we should do if we want to return these concatenate numbers in ascending order?

Question:

Given a unsorted list of positive numbers, you can concatenate them into one number in any order, how to print all unique possible numbers in ascending order?

For example, for input 2, 3, 1(or whatever order), the output would be always a sorted list of 6 integers: 123, 132, 213, 231, 312, 321.

Answer:

The main logic would still be same as the previous post. The main difference is how to ensure the returned concatenate numbers are sorted in ascending order?

One obvious way is that we sort the returned result, but this would take more time, the length of the result would be n!, so the time complexity would be O(n!log(n!)). This is undesired.

First we sort the parameter list in ascending order, then we assume the sub-result of a[1] to a[n-1] is sorted ascending order. When we add a[0] to all possible positions of previous sub result, what we need do to make the new list still sorted?

Take instance, for input, 3, 2, 1, first we sort them to 1, 2, 3, and assume the sub result of 2, 3 is sorted: [2,3], [3,2].

Now when add 1 to the zero index of [2,3], [3, 2], and we get [1,2,3], [1,3,2].

Now we loop each element, for each element, we add 1 to the possible positions from 1 to 2(length of the each element), so we get [2, 1, 3], [2, 3, 1], and [3, 1, 2], [3, 2, 1].

Code:

The complete algorithm/test code and also many other algorithm problems and solutions are available from https://github.com/programmer-plus.

package org.codeexample.concatNumber;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import org.codeexample.common.OverflowException;
import org.codeexample.common.Utils;
public class AllConcatNumberSorted {
 /**
  * This method would concatenate each integer value of the list in ascending
  * order.
  * 
  * @param la,
  *            a list of positive integer numbers
  * @return all unique concatenate integer numbers from the list in ascending
  *         order.
  * @throws IllegalArgumentException,
  *             if the parameter list contains negative value.
  * @throws OverflowException,
  *             it one possible concatenate integer number is greater than
  *             Integer.MAX_VALUE
  */
 public static List<Integer< concatNumbersSored(
   List<Integer< la)
   throws IllegalArgumentException,
   OverflowException {
  Collections.sort(la);
  Set<List<Integer<< permutations = concatNumbersSortedImpl(
    la, 0);
  List<Integer< results = new ArrayList<Integer<();
  for (List<Integer< intList : permutations) {
   int result = 0;
   for (int tmpInt : intList) {
    result = Utils.concat(result, tmpInt);
   }
   results.add(result);
  }
  return results;
 }
 private static Set<List<Integer<< concatNumbersSortedImpl(
   List<Integer< la, int level) {
  // use linked hash set to keep the inserted order.
  Set<List<Integer<< permutations = new LinkedHashSet<List<Integer<<();
  // base case
  if (level == la.size() - 1) {
   if (la.get(level) < 0)
    throw new IllegalArgumentException(
      "Invalid number: " + la.get(level));
   List<Integer< result = new LinkedList<Integer<();
   result.add(la.get(level));
   permutations
     .add(new LinkedList<Integer<(result));
   return permutations;
  }
  int head = la.get(level);
  if (head < 0)
   throw new IllegalArgumentException(
     "Invalid number: " + head);
  Set<List<Integer<< subPermutations = concatNumbersSortedImpl(
    la, ++level);
  // first insert head to the first position of the sub result
  for (List<Integer< tmpList : subPermutations) {
   List<Integer< tmp = new LinkedList<Integer<(
     tmpList);
   tmp.add(0, head);
   permutations.add(tmp);
  }
  for (List<Integer< tmpList : subPermutations) {
   // add head to other possible n positions
   for (int i = 1; i <= tmpList.size(); i++) {
    List<Integer< tmp = new LinkedList<Integer<(
      tmpList);
    tmp.add(i, head);
    permutations.add(tmp);
   }
  }
  return permutations;
 }
}