如何在我的Java代码中替代递归?

huangapple go评论63阅读模式
英文:

How to replace recursion in my code on Java?

问题

这段代码计算了四个点中选择三个点的排列数(无重复)。原始的递归方法是这样的:

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);
            }
        }
    }
}

你想要去除递归调用,但是你的尝试没有成功。这里是一个替代方法:

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);
                }
            }
        }
    }
}

这个替代方法使用了一个while循环来生成排列,而不是递归调用。

英文:

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(&quot;no repetitions:&quot;);
        p1(0,0, points);
    }

    static void p1(int nowPosition, int sizeArray, int[] points) {
        if (nowPosition == POINTS_ON_LINE) {
            System.out.println(&quot;Output:&quot;);
            System.out.println(Arrays.toString(temp));
        } else {
            for(int i = sizeArray + 1; i &lt;= 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(&quot;no repetitions:&quot;);
        p1(points);
    }

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

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

            if(nowPosition == POINTS_ON_LINE) {
                System.out.println(&quot;Output: &quot; + 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(&quot;no repetitions:&quot;);
        p1(points, POINTS_ON_LINE);
    }

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

        List&lt;Integer&gt; indices = IntStream.range(0, base).boxed().collect(Collectors.toList());

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

        if (base &lt; SIZE_ARRAY) {
            System.out.println(&quot;first&quot;);


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

            while (true) {
                flag = false;
                for (i = base - 1; i &gt;= 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 &lt; base; j++)
                    indices.set(j, indices.get(j - 1) + 1);
                System.out.println(indices.stream().map(idx -&gt; arr[idx]).collect(Collectors.toList()));

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

答案1

得分: 0

import itertools

TOTAL_POINTS = 4
POINTS_ON_LINE = 3
temp = [0] * POINTS_ON_LINE

def main():
    points = [1, 2, 3, 4]

    print("no repetitions:")
    p1(points, POINTS_ON_LINE)

def p1(arr, r):
    n = len(arr)
    indices = list(range(r))

    if r < n:
        for idx in indices:
            temp[idx] = arr[idx]
        print(temp)

        while True:
            flag = False
            for i in range(r - 1, -1, -1):
                if indices[i] != i + n - r:
                    flag = True
                    break
            if not flag:
                return
            indices[i] += 1
            for j in range(i + 1, r):
                indices[j] = indices[j - 1] + 1

            for i in range(r):
                temp[i] = arr[indices[i]]
            print(temp)

if __name__ == "__main__":
    main()
英文:

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(&quot;no repetitions:&quot;);
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 &lt; r; i++)
indices[i] = i;
if (r &lt; 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 &gt;= 0; i--)
if (indices[i] != i + n - r) {
flag = true;
break;
}
if (!flag)
return;
indices[i] += 1;
for (int j = i + 1; j &lt; r; j++)
indices[j] = indices[j - 1] + 1;
for (i = 0; i &lt; r; i++)
temp[i] = arr[indices[i]];
System.out.println(Arrays.toString(temp));
}
}
}
}

huangapple
  • 本文由 发表于 2020年8月23日 03:27:34
  • 转载请务必保留本文链接:https://go.coder-hub.com/63540279.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定