我想打印所有按升序排列的数字组合。输出应该是：012013014。。。，789，对于n＝3。我试图使用递归来解决它，但是我遇到了StackOverflowError。所以这意味着它永远不会达到结果。这是我到目前为止的代码：
public class Main {
public static void main(String[] args) {
int[] a = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0};
print_combinations(a, 0, 3);
}
static void print_combinations(int[] a, int index, int n) {
if (n > 0 && n < 10) {
if (index == n - 1) {
if (is_ascending(a, n)) {
System.out.print(Arrays.toString(a));
System.out.print(", ");
}
if (!has_ended(a, n)) {
print_combinations(a, 0, n);
}
} else {
while (a[index] <= 9 - n + index - 1) {
print_combinations(a, index + 1, n);
if (index < n - 1 && a[index] == 9 - n + index - 1) {
a[index + 1] = 0;
}
a[index]++;
}
}
}
}
static boolean has_ended(int[] a, int n) {
int ctr = 0;
while (ctr < n) {
if (a[ctr] != 10 - n + ctr) {
return false;
} else {
ctr++;
}
}
return true;
}
static boolean is_ascending(int[] a, int n) {
int ctr = 0;
while (ctr < n - 1) {
if (a[ctr] >= a[ctr + 1]) {
return false;
}
ctr++;
}
return true;
}
}```
您的代码中存在以下问题：
-
基本情况不是
if (index == n - 1)，因为那时您仍然需要填充a[index]的不同数字。基本情况是当if (index == n)。 -
一旦处理了基本情况，就应该而不是进行更深入的递归调用，就像处理
if (!has_ended(a, n))块一样。不，递归的原理是，一旦到达搜索路径的末尾，就回溯，所以只需要返回即可。呼叫者将处理其他变体。应删除此if块。 -
while循环结束得太早。它的条件不应该是a[index] <= 9 - n + index - 1，而是a[index] <= 9 - n + index + 1。 -
该循环中的
if条件是测试错误的数组值，并与错误的极限进行比较。它不应该是a[index] == 9 - n + index - 1，而是a[index + 1] == 9 - n + index + 3。 -
使用
Arrays.toString(a)，您将获得a的所有10个条目，而不是其中的第一个n。你可以做Arrays.toString(Arrays.copyOfRange(a, 0, n))。
有了这些修复，你的代码就会正常工作：
static void print_combinations(int[] a, int index, int n) {
if (n > 0 && n < 10) {
if (index == n) {
if (is_ascending(a, n)) {
System.out.print(Arrays.toString(Arrays.copyOfRange(a, 0, n)));
System.out.print(", ");
}
} else {
while (a[index] <= 9 - n + index + 1) {
print_combinations(a, index + 1, n);
if (index < n - 1 && a[index + 1] == 9 - n + index + 3) {
a[index + 1] = 0;
}
a[index]++;
}
}
}
}
有更优雅的方法可以实现所需的输出，但至少这向您展示了代码的问题所在。
这里有一个版本，它不分配10个数组条目，但首先定义n，然后将其用于数组的动态长度。此外，不同数字之间的迭代可以用for循环来完成，您还可以添加逻辑，使其不是每次都从0开始，而是比左边的数字多开始一个。这样，您就不需要检查数组是否为升序，因为它是有保证的。
public static void main(String[] args) {
int n = 3;
int[] a = new int[n];
print_combinations(a, 0, n);
}
static void print_combinations(int[] a, int index, int n) {
if (index == n) {
System.out.print(Arrays.toString(a));
System.out.print(", ");
} else {
int first = index > 0 ? a[index - 1] + 1 : 0;
int last = 10 - n + index;
for (int digit = first; digit <= last; digit++) {
a[index] = digit;
print_combinations(a, index + 1, n);
}
}
}
print_combinations本身被递归调用数十万次，直到溢出。
a[index]++;
在print_combinations中从未达到，因为在！has_end check。
这意味着while循环中除print_combinations调用外的所有调用都是不可访问的。
我个人的建议是，只需像下面的例子一样增加一个整数，只需使用一点时髦的编程来检查升序，只需修改代码使其工作，但可能有更好的方法。
public class TestCode {
public static void main(String[] args) {
int a = 0;
int n = 4;
TestCode test = new TestCode();
while(Integer.toString(a).length() < n-1){
a++;
}
while(Integer.toString(a).length() <= n){
test.print_combinations(a, 0, n);
a++;
}
}
public void print_combinations(int a, int index, int n) {
char[] print = new char[n];
char[] test = Integer.toString(a).toCharArray();
if(test.length < n && test.length >= n - 1){
print = new char[test.length+1];
for(int x = 0; x <= test.length; x++){
if(x == 0){
print[x] = '0';
}else{
print[x] = test[x-1];
}
}
if(this.is_ascending(print, n)){
System.out.println(new String(print));
}
}else if(this.is_ascending(test, n)){
System.out.println(new String(test));
}
}
public boolean is_ascending(char[] a, int n) {
int ctr = 0;
while (ctr < n - 1) {
if (Character.getNumericValue(a[ctr]) >= Character.getNumericValue(a[ctr + 1])) {
return false;
}
ctr++;
}
return true;
}
}
或者，如果你一心想使用数组，可以做完全相反的事情，检查降序，当你打印出来时，使用之类的东西
System.out.println("" + a[index +2] + a[index +1] + a[index])
这将获取[9,7,4]的数组并将其打印为"0"；479〃；
这样做将极大地简化与阵列的交互，并减少递归的需要，因为您是从阵列的前端工作的，并使故障排除更加容易。