Find all Concatenate Numbers - Unsorted

Question:

Given a list of positive numbers, you can concatenate them into one number in any order, how to print all unique possible numbers? In this question, the order of the result is not important.

For example, for input 1, 2, 3, the output would be a list of 6 integers: 123, 132, 213, 231, 312, 321.

Answer:

This is a classical dynamic programming problems, we can divide the integer list to two parts, a0, and [a, .., an-1], so if we know the result of the sub list[a, .., an-1], we can compute result of the whole integer list.

Take example, for 1, 23, 45. First, we compute the sub-result of 23, 45, the result would be [[23, 45], [45, 23]], then for each member of the sub-result, we add 1 to all possible positions.

First we add 1 to all possible positions of [23, 45], we will get three integer list, [[1, 23, 45], [23, 1, 45], [23, 45, 1]], then we add 1 to add 1 to all possible positions of [45, 23], the result would be [1, 45, 23], [45, 1, 23], [45, 23, 1]. So the all possible concatenate numbers of 1, 23, 45 would be 12345, 23145, 23451, 14523, 45123, 45231.

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.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import org.codeexample.common.OverflowException;
import org.codeexample.common.Utils;
public class AllConcatNumberUnsorted {
 /**
  * This method would concatenate each integer value of the list in any
  * order.
  * 
  * @param la,
  *            a list of positive integer numbers
  * @return all unique concatenate integer numbers from the list
  * @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> concatNumbersUnsored(
   List<Integer> la)
   throws IllegalArgumentException,
   OverflowException {
  HashSet<List<Integer>> permutations = concatNumbersUnSortedImpl(
    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 HashSet<List<Integer>> concatNumbersUnSortedImpl(
   List<Integer> la, int level) {
  HashSet<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);
  HashSet<List<Integer>> subPermutations = concatNumbersUnSortedImpl(
    la, ++level);
  for (List<Integer> tmpList : subPermutations) {
   // add head to all possible n+1 positions
   for (int i = 0; i <= tmpList.size(); i++) {
    List<Integer> tmp = new LinkedList<Integer>(
      tmpList);
    tmp.add(i, head);
    permutations.add(tmp);
   }
  }
  return permutations;
 }
}