I want to print all number combinations that are in ascending order. The output should go like: 012, 013, 014, ..., 789 for n = 3. I tried to solve it using recursion, however I'm having the StackOverflowError. So it means it never reaches the result. Here is my code so far:
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;
}
}```
CodePudding user response：
print_combinations is being called recursively by itself hundreds of thousands of times until it overflows.
a[index] ;
is never reached in print_combinations due to index constantly being reset to 0 after the !has_ended check.
This means that all but the print_combinations call in the while loop are unreachable.
My personal recommendation is to just increment an integer like the example below and just use a bit of funky programming to check the ascending bit, just modifying your code to make it work but there are probably better ways.
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;
}
}
Alternatively, if you're absolutely hellbent on using arrays, do the exact opposite, check for descending and when you print it out use something like
System.out.println("" a[index 2] a[index 1] a[index])
This will grab an array of [9,7,4] and print it out as "479"
Doing it this way will drastically ease your interactions with arrays and reduce the need for recursions since you're working from the front of the array and make troubleshooting far easier.
CodePudding user response：
There are these issues in your code:
The base case is not when
if (index == n - 1), because then you still need to populatea[index]will different digits. The base case is whenif (index == n).Once the base case is treated, you should not make even deeper recursive calls, as you do with the
if (!has_ended(a, n))block. No, the principle of recursion is that you backtrack once you have reached the end of a search path, so you simply need to return. The caller will deal with other variations. Thisifblock should be removed.The
whileloop ends too soon. Its condition should not bea[index] <= 9 - n index - 1, buta[index] <= 9 - n index 1.The
ifcondition inside that loop is testing the wrong array value, and comparing with the wrong limit. It should not bea[index] == 9 - n index - 1, buta[index 1] == 9 - n index 3.With
Arrays.toString(a)you'll get all 10 entries ofainstead of the firstnof them. You could doArrays.toString(Arrays.copyOfRange(a, 0, n)).
With those fixes your code will work:
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] ;
}
}
}
}
There are more elegant ways to achieve the desired output, but at least this shows you where your code had issues.
Here is a version that does not allocate 10 array entries, but first defines n and then uses that for a dynamic length for the array. Also, the iteration over the different digits can be done with a for loop, and you can also add logic to not start each time at 0, but at one more than the digit at the left. This way you don't need the check whether the array is ascending, as it is then guaranteed.
public static void main(String[] args) {
int n = 3;
int[] a = new int[n];
print_combinations(a, 0, 3);
}
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);
}
}
}