Printing all factorizations of a number

Question 1

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]

Question 2

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$
$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 $2 \cdot 65$

2 \cdot 65

$2 cdot 65$ and $5 \cdot 26$

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) {
    // 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]

Leave a Reply Cancel reply