英文:
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("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);
}
}
}
}
}
答案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("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));
}
}
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论