How to replace recursion in my code on Java?

Question

This code calculates the number of permutations for four points by 3 (no repetitions). Arranged with recursion, but this is awkward for me.

import java.util.*;

public class Main {

    static int TOTAL_POINTS = 4, POINTS_ON_LINE = 3;

    static int[] temp = new int[POINTS_ON_LINE];

    public static void main(String[] args) {
        int[] points = new int[]{1,2,3,4};

        System.out.println("no repetitions:");
        p1(0,0, points);
    }

    static void p1(int nowPosition, int sizeArray, int[] points) {
        if (nowPosition == POINTS_ON_LINE) {
            System.out.println("Output:");
            System.out.println(Arrays.toString(temp));
        } else {
            for(int i = sizeArray + 1; i <= TOTAL_POINTS; i++) {
                temp[nowPosition] = points[i-1];
                p1(nowPosition + 1, i, points);
            }
        }
    }
}

Output:

no repetitions:
Output:
[1, 2, 3]
Output:
[1, 2, 4]
Output:
[1, 3, 4]
Output:
[2, 3, 4]

It is necessary to get rid of the recursive method call p1. I tried to do so:

import java.util.*;

public class Main {

    static int TOTAL_POINTS = 4, POINTS_ON_LINE = 3;

    static int[] temp = new int[POINTS_ON_LINE];

    public static void main(String[] args) {
        int[] points = new int[]{1,2,3,4};

        System.out.println("no repetitions:");
        p1(points);
    }

    static void p1(int[] points) {
        int sizeArray = points.length;

        for(int i = sizeArray + 1; i < TOTAL_POINTS; i++, sizeArray = i) {
            int nowPosition = 0;

            if(nowPosition == POINTS_ON_LINE) {
                System.out.println("Output: " + Arrays.toString(temp));
            } else {
                temp[nowPosition] = points[i-1];
                nowPosition++;
            }
        }
    }
}

Result - Output on console - empty. It didn't work for me. How to replace recursion?

Method # 1 (thanks for the suggested option - @deadshot)

package com.company;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

    static int TOTAL_POINTS = 4, POINTS_ON_LINE = 3;
    static int[] temp = new int[POINTS_ON_LINE];

    public static void main(String[] args) {
        int[] points = new int[]{1, 2, 3, 4};

        System.out.println("no repetitions:");
        p1(points, POINTS_ON_LINE);
    }

    public static void p1(int[] arr, int base) {
        int SIZE_ARRAY = arr.length;

        List<Integer> indices = IntStream.range(0, base).boxed().collect(Collectors.toList());

        for(Integer i : indices) {
            System.out.println("- " + i);
        }

        if (base < SIZE_ARRAY) {
            System.out.println("first");


            System.out.println(indices.stream().map(idx -> arr[idx]).collect(Collectors.toList()));
            boolean flag;
            int i;

            while (true) {
                flag = false;
                for (i = base - 1; i >= 0; i--)
                    if (indices.get(i) != i + SIZE_ARRAY - base) {
                        flag = true;
                        break;
                    }
                if (!flag)
                    return;
                indices.set(i, indices.get(i) + 1);
                for (int j = i + 1; j < base; j++)
                    indices.set(j, indices.get(j - 1) + 1);
                System.out.println(indices.stream().map(idx -> arr[idx]).collect(Collectors.toList()));

                for(Integer x : indices) {
                    System.out.println("- " + x);
                }
            }
        }
    }
}

It seems you forgot to invoke p1 method from your main method. — SKumar, Aug 22 '20 at 19:37
@SKumar, Ohh, just forgot add on this code. But that doesn't change the result — West Side, Aug 22 '20 at 19:40
The for loop initiazer code could be the culprit. i starts with 5 in your code but the loop code can only execute if it's less than 4. — SKumar, Aug 22 '20 at 19:48
this will help https://github.com/samagra14/itertools_java#12-itertoolscombinationslistt-list-int-r — deadshot, Aug 22 '20 at 20:19
your code not works. even if it works it will not give the expected output — deadshot, Aug 22 '20 at 20:27
@deadshot, the code works as it should and it is shown in the topic — West Side, Aug 22 '20 at 20:46
can you explain how it works? no one written the code to generate combinations of a list in O(n). You are the first if it works — deadshot, Aug 22 '20 at 20:49
@deadshot, input {1,2,3,4}. N = 4, K = 3. Output combinations: `Output: [1, 2, 3] Output: [1, 2, 4] Output: [1, 3, 4] Output: [2, 3, 4]` — West Side, Aug 22 '20 at 20:53
it's already there in the post. what i'm asking is "the code works as it should and it is shown in the topic" how it works? — deadshot, Aug 22 '20 at 20:58
@deadshot, you write that it does not work correctly. Give a concrete example of what is wrong — West Side, Aug 22 '20 at 21:18
no example is needed how can you generate a combinations of a list with using one loop — deadshot, Aug 22 '20 at 21:27
@deadshot, Just tell me, is the result wrong? All works. So the code is working with one loop `for` + `recursion`. — West Side, Aug 22 '20 at 21:34
in recursive implementation every function call using the loop — deadshot, Aug 22 '20 at 21:44
@deadshot, I can't figure out how to do this without recursion — West Side, Aug 23 '20 at 08:00

deadshot · Accepted Answer · 2020-08-23T10:28:01.787

0

I have used python itertools.combinations code as reference to implement the method.

public class Main {

    static int TOTAL_POINTS = 4, POINTS_ON_LINE = 3;
    static int[] temp = new int[POINTS_ON_LINE];

    public static void main(String[] args) {
        int[] points = new int[]{1, 2, 3, 4};

        System.out.println("no repetitions:");
        p1(points, POINTS_ON_LINE);
    }

    public static void p1(int[] arr, int r) {
        int n = arr.length, i;
        int[] indices = new int[r];

        for (i = 0; i < r; i++)
            indices[i] = i;

        if (r < n) {
            for (int idx : indices)
                temp[idx] = arr[idx];
            System.out.println(Arrays.toString(temp));

            boolean flag;
            while (true) {
                flag = false;
                for (i = r - 1; i >= 0; i--)
                    if (indices[i] != i + n - r) {
                        flag = true;
                        break;
                    }
                if (!flag)
                    return;
                indices[i] += 1;
                for (int j = i + 1; j < r; j++)
                    indices[j] = indices[j - 1] + 1;

                for (i = 0; i < r; i++)
                    temp[i] = arr[indices[i]];
                System.out.println(Arrays.toString(temp));
            }
        }
    }
}

edited Aug 23 '20 at 10:28

answered Aug 23 '20 at 09:56

deadshot

8,881
4
20
39

what mean this `List indices = IntStream.range(0, base).boxed().collect(Collectors.toList());` and ` System.out.println(indices.stream().map(idx -> arr[idx]).collect(Collectors.toList()));` ? This two lines - too hard for me – West Side Aug 23 '20 at 10:12
it's just a way of creating list using streams. this will help [How do I convert a Java 8 IntStream to a List?](https://stackoverflow.com/questions/23674624/how-do-i-convert-a-java-8-intstream-to-a-list) – deadshot Aug 23 '20 at 10:15
could you help me - write more simple this two lines of code? – West Side Aug 23 '20 at 10:17
first - `List indices = IntStream.range(0, r).boxed().collect(Collectors.toList());`, second - `System.out.println(indices.stream().map(idx -> arr[idx]).collect(Collectors.toList()));`. – West Side Aug 23 '20 at 10:19
thank you so much! Please, tell me about this moment. Now started reading about the class `IntStream`. Ok. Class `IntStream` have method `range`, that `Returns a sequential ordered IntStream from srart_value (inclusive) to end_value (inclusive) by an incremental step of 1.`. Ok, that understand. Method `boxed()` is `Returns a Stream consisting of the elements of this stream, each boxed to an Integer. `. But i don't understand, how this line of code `List indices = IntStream.range(0, r).boxed().collect(Collectors.toList());` write like this: `there was one dot in one line`? – West Side Aug 23 '20 at 10:36
but i removed those lines and used normal for loop check the code. answer to your question `collect()` is a terminal method in stream by using this we can convert the result to list, set, map, etc... – deadshot Aug 23 '20 at 10:37
yeah, I have seen., thanks. But I also need to figure out what code before. Update topic (add your first answer) – West Side Aug 23 '20 at 10:40
because wanna see more simple method. When I saw more simple method - wanna make more "hard" method :) It is not known how much time I would spend to deal with a more complex option. – West Side Aug 23 '20 at 10:45
can you please tell me correctly what exactly are you expecting from this code? are you getting any errors with this code – deadshot Aug 23 '20 at 10:48
no this code is correct! Thank you. `IntStream intStream = IntStream.range(0, base);` `Stream stream = intStream.boxed();` `List index = stream.collect(Collectors.toList());` – West Side Aug 23 '20 at 10:49
then what is your question I don't understand? – deadshot Aug 23 '20 at 10:54
what type of data return in this case code `List index = WHAT_TYPE`? I don't understand. – West Side Aug 23 '20 at 10:55
`List index` it's a list of integers – deadshot Aug 23 '20 at 10:58
`List index` - this is interface. Should be like this `List index = new ArrayList<>();` – West Side Aug 23 '20 at 10:59
`IntStream.range(0, r).boxed().collect(Collectors.toList())` this will return a list to store this i used `List index` – deadshot Aug 23 '20 at 11:04
In other words, `interface List` ? – West Side Aug 23 '20 at 11:07
everything is fine, just clarifying the implementation details :) – West Side Aug 23 '20 at 11:10

How to replace recursion in my code on Java?

1 Answers1

Linked