Recursive number permutation in Java

Question

Recently I got assigned an assignment that says this:

Write a program named NumberPermutation.java and implement a recursive method specified below:
public static void permutation(int num)
This method has a positive integer as its parameter and displays all permutations of the odd digits of that length.

Display these values in ascending order. For example, if the length is 3, your program should display:
111
113
115
117
119
131
133
135
...

I'm very new to Java (as in all my previous coding assignments for the past year have been in Python and this is the 3rd Java program I've worked on), so I am absolutely lost on where to even get started. If anyone can lend a hand and tell me how to get started I'd appreciate it, thanks.

score 0 · Answer 1 · edited Jul 18 '21 at 20:30

Although I don't like questions that smell "help me with my homework" I'll provide an answer this time. Here's my suggestion. Please don't just copy and paste and hand in. Understand first, and use this example to understand some of the basics of Java.

public class RecursionTester {
    public static void main(String[] args) {
        new RecursionTester().permutation(3);
    }

    private void permutation(int num) {
        permutation(num, "");
    }

    private void permutation(int num, String buffer) {
        if (num == 0) {
            System.out.println(buffer);
            return;
        }
        for (int i = 1; i < 10; i += 2) {
            permutation(num - 1, buffer + Integer.toString(i));
        }
    }
}

The fact that the results just go to System.out makes this solution pretty useless, but if the task is to only prove that you understand recursion it should be enough.

score 0 · Answer 2 · 2021-07-19T21:47:13.763

The map and reduce approach

You can interpret this task as getting the Cartesian product of the n-th number of 2D arrays of odd digits. If n=3 then you get 5³=125 combinations.

The mapToObj method prepares 2D arrays for summation and points to the format of the result:

1: {{1}, {3}, {5}, {7}, {9}}
2: {{1}, {3}, {5}, {7}, {9}}
3: {{1}, {3}, {5}, {7}, {9}}

The reduce method sums pairs of 2D arrays into a single 2D array - two steps of reduction if n=3:

1: {{1}, {3}, {5}, {7}, {9}}
2: {{1}, {3}, {5}, {7}, {9}}
---
sum1: {{1, 1}, {1, 3}, {1, 5}, ...}
3: {{1}, {3}, {5}, {7}, {9}}
---
total: {1, 1, 1}, {1, 1, 3}, ...}

Try it online!

public static int[][] cartesianProduct(int n, int[][] arr) {
    return IntStream.range(0, n)
            // stream of n-th number of 2D arrays
            .mapToObj(i -> arr)
            // stream of 2D arrays into a single 2D array
            .reduce((arr1, arr2) -> Arrays.stream(arr1)
                // combinations of rows of two arrays
                .flatMap(row1 -> Arrays.stream(arr2)
                    // concatenate into a single row
                    .map(row2 -> Stream.of(row1, row2)
                        .flatMapToInt(Arrays::stream)
                        // row of a 2D array
                        .toArray()))
                // 2D array of combinations
                .toArray(int[][]::new))
            // otherwise an empty array
            .orElse(new int[0][]);
}

public static void main(String[] args) {
    // exponent
    int n = 3;
    // 2D array of odd digits
    int[][] arr = {{1}, {3}, {5}, {7}, {9}};
    // cartesian product
    int[][] cp = cartesianProduct(n, arr);
    // output
    System.out.println("Number of combinations: " + cp.length);
    // number of rows
    int rows = cp.length / arr.length;
    // column-wise output
    IntStream.range(0, rows)
            .mapToObj(i -> IntStream.range(0, cp.length)
                .filter(j -> j % rows == i)
                .mapToObj(j -> Arrays.toString(cp[j]))
                .collect(Collectors.joining(" ")))
            .forEach(System.out::println);
}

Output:

Number of combinations: 125
[1, 1, 1] [3, 1, 1] [5, 1, 1] [7, 1, 1] [9, 1, 1]
[1, 1, 3] [3, 1, 3] [5, 1, 3] [7, 1, 3] [9, 1, 3]
[1, 1, 5] [3, 1, 5] [5, 1, 5] [7, 1, 5] [9, 1, 5]
[1, 1, 7] [3, 1, 7] [5, 1, 7] [7, 1, 7] [9, 1, 7]
[1, 1, 9] [3, 1, 9] [5, 1, 9] [7, 1, 9] [9, 1, 9]
[1, 3, 1] [3, 3, 1] [5, 3, 1] [7, 3, 1] [9, 3, 1]
[1, 3, 3] [3, 3, 3] [5, 3, 3] [7, 3, 3] [9, 3, 3]
[1, 3, 5] [3, 3, 5] [5, 3, 5] [7, 3, 5] [9, 3, 5]
[1, 3, 7] [3, 3, 7] [5, 3, 7] [7, 3, 7] [9, 3, 7]
[1, 3, 9] [3, 3, 9] [5, 3, 9] [7, 3, 9] [9, 3, 9]
[1, 5, 1] [3, 5, 1] [5, 5, 1] [7, 5, 1] [9, 5, 1]
[1, 5, 3] [3, 5, 3] [5, 5, 3] [7, 5, 3] [9, 5, 3]
[1, 5, 5] [3, 5, 5] [5, 5, 5] [7, 5, 5] [9, 5, 5]
[1, 5, 7] [3, 5, 7] [5, 5, 7] [7, 5, 7] [9, 5, 7]
[1, 5, 9] [3, 5, 9] [5, 5, 9] [7, 5, 9] [9, 5, 9]
[1, 7, 1] [3, 7, 1] [5, 7, 1] [7, 7, 1] [9, 7, 1]
[1, 7, 3] [3, 7, 3] [5, 7, 3] [7, 7, 3] [9, 7, 3]
[1, 7, 5] [3, 7, 5] [5, 7, 5] [7, 7, 5] [9, 7, 5]
[1, 7, 7] [3, 7, 7] [5, 7, 7] [7, 7, 7] [9, 7, 7]
[1, 7, 9] [3, 7, 9] [5, 7, 9] [7, 7, 9] [9, 7, 9]
[1, 9, 1] [3, 9, 1] [5, 9, 1] [7, 9, 1] [9, 9, 1]
[1, 9, 3] [3, 9, 3] [5, 9, 3] [7, 9, 3] [9, 9, 3]
[1, 9, 5] [3, 9, 5] [5, 9, 5] [7, 9, 5] [9, 9, 5]
[1, 9, 7] [3, 9, 7] [5, 9, 7] [7, 9, 7] [9, 9, 7]
[1, 9, 9] [3, 9, 9] [5, 9, 9] [7, 9, 9] [9, 9, 9]

^{See also: How do I generate a Cartesian product in Java?}

Recursive number permutation in Java

2 Answers2

The map and reduce approach