Printing all factorizations of a number

Posted on

Problem

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>();
if (isPrime(n)) {
return possprod;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
for (String y : getPossibleProducts2(n / i)) {
}
}
}
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);
}
}
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]


Solution

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”

Your code is ineffective for two reasons:

• The first method finds all factorizations with all possible permutations
(e.g. 120=260=602

$120=2\cdot 60=60\cdot 2$

$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

$n=1024$

$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. “2×60”, “60×2”) which then have to be split into integer arrays again.

To find duplicate factorizations, you split the string (e.g. “60×2”)
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

$n=130$

$n = 130$,
the factorizations 265

$2\cdot 65$

$2 cdot 65$ and 526

$5\cdot 26$

$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) {
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).
} 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);

// ... 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]