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

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

How to replace recursion in my code on Java?

问题

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

  1. import java.util.*;
  3. public class Main {
  5.     static int TOTAL_POINTS = 4, POINTS_ON_LINE = 3;
  7.     static int[] temp = new int[POINTS_ON_LINE];
  9.     public static void main(String[] args) {
  10.         int[] points = new int[]{1,2,3,4};
  12.         System.out.println("no repetitions:");
  13.         p1(0,0, points);
  14.     }
  16.     static void p1(int nowPosition, int sizeArray, int[] points) {
  17.         if (nowPosition == POINTS_ON_LINE) {
  18.             System.out.println("Output:");
  19.             System.out.println(Arrays.toString(temp));
  20.         } else {
  21.             for(int i = sizeArray + 1; i <= TOTAL_POINTS; i++) {
  22.                 temp[nowPosition] = points[i-1];
  23.                 p1(nowPosition + 1, i, points);
  24.             }
  25.         }
  26.     }
  27. }

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

  1. import java.util.*;
  2. import java.util.stream.Collectors;
  3. import java.util.stream.IntStream;
  5. public class Main {
  7.     static int TOTAL_POINTS = 4, POINTS_ON_LINE = 3;
  8.     static int[] temp = new int[POINTS_ON_LINE];
  10.     public static void main(String[] args) {
  11.         int[] points = new int[]{1, 2, 3, 4};
  13.         System.out.println("no repetitions:");
  14.         p1(points, POINTS_ON_LINE);
  15.     }
  17.     public static void p1(int[] arr, int base) {
  18.         int SIZE_ARRAY = arr.length;
  20.         List<Integer> indices = IntStream.range(0, base).boxed().collect(Collectors.toList());
  22.         for(Integer i : indices) {
  23.             System.out.println("- " + i);
  24.         }
  26.         if (base < SIZE_ARRAY) {
  27.             System.out.println("first");
  29.             System.out.println(indices.stream().map(idx -> arr[idx]).collect(Collectors.toList()));
  30.             boolean flag;
  31.             int i;
  33.             while (true) {
  34.                 flag = false;
  35.                 for (i = base - 1; i >= 0; i--)
  36.                     if (indices.get(i) != i + SIZE_ARRAY - base) {
  37.                         flag = true;
  38.                         break;
  39.                     }
  40.                 if (!flag)
  41.                     return;
  42.                 indices.set(i, indices.get(i) + 1);
  43.                 for (int j = i + 1; j < base; j++)
  44.                     indices.set(j, indices.get(j - 1) + 1);
  45.                 System.out.println(indices.stream().map(idx -> arr[idx]).collect(Collectors.toList()));
  47.                 for(Integer x : indices) {
  48.                     System.out.println("- " + x);
  49.                 }
  50.             }
  51.         }
  52.     }
  53. }

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

英文:

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

  1. import java.util.*;
  3. public class Main {
  5.     static int TOTAL_POINTS = 4, POINTS_ON_LINE = 3;
  7.     static int[] temp = new int[POINTS_ON_LINE];
  9.     public static void main(String[] args) {
  10.         int[] points = new int[]{1,2,3,4};
  12.         System.out.println(&quot;no repetitions:&quot;);
  13.         p1(0,0, points);
  14.     }
  16.     static void p1(int nowPosition, int sizeArray, int[] points) {
  17.         if (nowPosition == POINTS_ON_LINE) {
  18.             System.out.println(&quot;Output:&quot;);
  19.             System.out.println(Arrays.toString(temp));
  20.         } else {
  21.             for(int i = sizeArray + 1; i &lt;= TOTAL_POINTS; i++) {
  22.                 temp[nowPosition] = points[i-1];
  23.                 p1(nowPosition + 1, i, points);
  24.             }
  25.         }
  26.     }
  27. }

Output:

  1. no repetitions:
  2. Output:
  3. [1, 2, 3]
  4. Output:
  5. [1, 2, 4]
  6. Output:
  7. [1, 3, 4]
  8. Output:
  9. [2, 3, 4]

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

  1. import java.util.*;
  3. public class Main {
  5.     static int TOTAL_POINTS = 4, POINTS_ON_LINE = 3;
  7.     static int[] temp = new int[POINTS_ON_LINE];
  9.     public static void main(String[] args) {
  10.         int[] points = new int[]{1,2,3,4};
  12.         System.out.println(&quot;no repetitions:&quot;);
  13.         p1(points);
  14.     }
  16.     static void p1(int[] points) {
  17.         int sizeArray = points.length;
  19.         for(int i = sizeArray + 1; i &lt; TOTAL_POINTS; i++, sizeArray = i) {
  20.             int nowPosition = 0;
  22.             if(nowPosition == POINTS_ON_LINE) {
  23.                 System.out.println(&quot;Output: &quot; + Arrays.toString(temp));
  24.             } else {
  25.                 temp[nowPosition] = points[i-1];
  26.                 nowPosition++;
  27.             }
  28.         }
  29.     }
  30. }

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

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

  1. package com.company;
  3. import java.util.*;
  4. import java.util.stream.Collectors;
  5. import java.util.stream.IntStream;
  7. public class Main {
  9.     static int TOTAL_POINTS = 4, POINTS_ON_LINE = 3;
  10.     static int[] temp = new int[POINTS_ON_LINE];
  12.     public static void main(String[] args) {
  13.         int[] points = new int[]{1, 2, 3, 4};
  15.         System.out.println(&quot;no repetitions:&quot;);
  16.         p1(points, POINTS_ON_LINE);
  17.     }
  19.     public static void p1(int[] arr, int base) {
  20.         int SIZE_ARRAY = arr.length;
  22.         List&lt;Integer&gt; indices = IntStream.range(0, base).boxed().collect(Collectors.toList());
  24.         for(Integer i : indices) {
  25.             System.out.println(&quot;- &quot; + i);
  26.         }
  28.         if (base &lt; SIZE_ARRAY) {
  29.             System.out.println(&quot;first&quot;);
  32.             System.out.println(indices.stream().map(idx -&gt; arr[idx]).collect(Collectors.toList()));
  33.             boolean flag;
  34.             int i;
  36.             while (true) {
  37.                 flag = false;
  38.                 for (i = base - 1; i &gt;= 0; i--)
  39.                     if (indices.get(i) != i + SIZE_ARRAY - base) {
  40.                         flag = true;
  41.                         break;
  42.                     }
  43.                 if (!flag)
  44.                     return;
  45.                 indices.set(i, indices.get(i) + 1);
  46.                 for (int j = i + 1; j &lt; base; j++)
  47.                     indices.set(j, indices.get(j - 1) + 1);
  48.                 System.out.println(indices.stream().map(idx -&gt; arr[idx]).collect(Collectors.toList()));
  50.                 for(Integer x : indices) {
  51.                     System.out.println(&quot;- &quot; + x);
  52.                 }
  53.             }
  54.         }
  55.     }
  56. }

答案1

得分: 0

  1. import itertools
  3. TOTAL_POINTS = 4
  4. POINTS_ON_LINE = 3
  5. temp = [0] * POINTS_ON_LINE
  7. def main():
  8.     points = [1, 2, 3, 4]
  10.     print("no repetitions:")
  11.     p1(points, POINTS_ON_LINE)
  13. def p1(arr, r):
  14.     n = len(arr)
  15.     indices = list(range(r))
  17.     if r < n:
  18.         for idx in indices:
  19.             temp[idx] = arr[idx]
  20.         print(temp)
  22.         while True:
  23.             flag = False
  24.             for i in range(r - 1, -1, -1):
  25.                 if indices[i] != i + n - r:
  26.                     flag = True
  27.                     break
  28.             if not flag:
  29.                 return
  30.             indices[i] += 1
  31.             for j in range(i + 1, r):
  32.                 indices[j] = indices[j - 1] + 1
  34.             for i in range(r):
  35.                 temp[i] = arr[indices[i]]
  36.             print(temp)
  38. if __name__ == "__main__":
  39.     main()
英文:

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

  1. public class Main {
  2. static int TOTAL_POINTS = 4, POINTS_ON_LINE = 3;
  3. static int[] temp = new int[POINTS_ON_LINE];
  4. public static void main(String[] args) {
  5. int[] points = new int[]{1, 2, 3, 4};
  6. System.out.println(&quot;no repetitions:&quot;);
  7. p1(points, POINTS_ON_LINE);
  8. }
  9. public static void p1(int[] arr, int r) {
  10. int n = arr.length, i;
  11. int[] indices = new int[r];
  12. for (i = 0; i &lt; r; i++)
  13. indices[i] = i;
  14. if (r &lt; n) {
  15. for (int idx : indices)
  16. temp[idx] = arr[idx];
  17. System.out.println(Arrays.toString(temp));
  18. boolean flag;
  19. while (true) {
  20. flag = false;
  21. for (i = r - 1; i &gt;= 0; i--)
  22. if (indices[i] != i + n - r) {
  23. flag = true;
  24. break;
  25. }
  26. if (!flag)
  27. return;
  28. indices[i] += 1;
  29. for (int j = i + 1; j &lt; r; j++)
  30. indices[j] = indices[j - 1] + 1;
  31. for (i = 0; i &lt; r; i++)
  32. temp[i] = arr[indices[i]];
  33. System.out.println(Arrays.toString(temp));
  34. }
  35. }
  36. }
  37. }

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

发表评论

匿名网友

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

确定