Printing all factorizations of a number

Question

For example, if we have 120, the answer should contain (2,2,2,3,5),(2,60),(4,30),...

Here is my not-so-good attempt

for (int[] x : getPossibleProducts(120)) {
 System.out.println(Arrays.toString(x));
}
public static List<String> getPossibleProducts2(int n) {
 List<String> possprod = new ArrayList<String>();
 possprod.add(n + "");
 if (isPrime(n)) {
 possprod.add(n + "");
 return possprod;
 }
 for (int i = 2; i * i <= n; i++) {
 if (n % i == 0) {
 for (String y : getPossibleProducts2(n / i)) {
 possprod.add(i + "x" + y);
 }
 }
 }
 return possprod;
}
public static List<int[]> getPossibleProducts(int n) {
 List<String> l = new ArrayList<String>();
 Set<int[]> set = new HashSet<int[]>();
 List<String> possprod = getPossibleProducts2(n);
 for (String x : possprod) {
 String[] y = x.split("x");
 Arrays.sort(y);
 if (!l.contains(Arrays.stream(y).reduce("", (a, b) -> a + b))) {
 l.add(Arrays.stream(y).reduce("", (a, b) -> a + b));
 int[] z = stringArraytoIntArray(y);
 set.add(z);
 }
 }
 return new ArrayList<int[]>(set);
}
public static int[] stringArraytoIntArray(String[] a) {
 int[] arr = new int[a.length];
 for (int i = 0; i < a.length; i++) {
 arr[i] = Integer.parseInt(a[i]);
 }
 return arr;
}
public static boolean isPrime(int i2) {
 if (i2 == 2)
 return true;
 if (i2 % 2 == 0)
 return false;
 for (int i = 3; i * i <= i2; i += 2)
 if (i2 % i == 0)
 return false;
 return true;
}

Here is the output:

[15, 8]
[10, 3, 4]
[30, 4]
[2, 3, 4, 5]
[12, 2, 5]
[10, 2, 2, 3]
[10, 12]
[120]
[15, 2, 2, 2]
[15, 2, 4]
[3, 40]
[4, 5, 6]
[2, 2, 5, 6]
[20, 6]
[2, 2, 30]
[2, 20, 3]
[2, 60]
[2, 2, 2, 3, 5]
[24, 5]
[10, 2, 6]
[3, 5, 8]

Answer 1

It is not immediately obvious that getPossibleProducts2() finds all factorizations and getPossibleProducts() removes the duplicates, so the names could be chosen better. (And I would use "factorizations" instead of "possibleProducts").

Your code is ineffective for two reasons:

• The first method finds all factorizations with all possible permutations (e.g. \$ 120 = 2 \cdot 60 = 60 \cdot 2 \$) so that you have to find the duplicates in a second step.

  As an example, for \$ n = 1024 \,ドル the first method computes 364176 factorizations, which are then reduced to 627 unique factorizations in the second step.

• You use strings to represents the factorizations (e.g. "2x60", "60x2") which then have to be split into integer arrays again.

To find duplicate factorizations, you split the string (e.g. "60x2") to an integer array ["60", "2"], sort the factors (["2", "60"]) then concatenate the factors again ("260"). This is used as a hash key to eliminate the duplicates. This is quite computing intensive. In particular the hash key

Arrays.stream(y).reduce("", (a, b) -> a + b))

is compute twice, and StringBuilder might be a more effective way to concatenate the array elements.

More important, it does not work: For \$ n = 130 \,ドル the factorizations \$ 2 \cdot 65 \$ and \$ 5 \cdot 26 \$ are both mapped to the same hash key "265", so that the output of your program is

[2, 65]
[13, 2, 5]
[10, 13]
[130]

without the factorization [5, 26].

Generally a better method would be to determine the factorizations without duplicates in the first step. This can be done recursively as follows:

• Find the smallest factor f of the given number n.
• Compute all factorizations of the n / f where the smallest factor is at least f.

This automatically leads to factorizations with the factors in increasing order and without duplicates.

As a side effect, the isPrime() function is not needed.

Here is a possible implementation. (Please take this as a demonstration of the algorithm only. Java is not my first language, so there may be more idiomatic ways to do implement this.)

public static List<int[]> factorizations(int n) {
 // Start with a minimum factor of 2:
 return factorizations(n, 2, new ArrayList<Integer>());
}
public static List<int[]> factorizations(int n, int minFactor, ArrayList<Integer> previousFactors) {
 List<int[]> result = new ArrayList<int[]>();
 if (n == 1) {
 // This is where the recursion terminates. Convert the list of
 // all previously found factors to an int[] array
 // (found here: http://stackoverflow.com/a/23945015/1187415).
 result.add(previousFactors.stream().mapToInt(i->i).toArray());
 } else {
 for (int factor = minFactor; factor <= n; factor++) {
 if (n % factor == 0) {
 // `factor` is a factor of `n`. Append it to (a clone of)
 // the previously found factors ...
 ArrayList<Integer> factors = new ArrayList<Integer>(previousFactors);
 factors.add(factor);
 // ... and (recursively) find all factorizations of `n / factor`
 // with factors greater or equal to `factor`:
 result.addAll( factorizations(n / factor, factor, factors) );
 }
 }
 }
 return result;
}

Example:

for (int[] f : factorizations(130)) {
 System.out.println(Arrays.toString(f));
}

produces the output

[2, 5, 13]
[2, 65]
[5, 26]
[10, 13]
[130]