Pattern Generation Recursion

Question

I'm writing a program to generate all possible combination of a string 1*0* by replacing * by 0 or 1. This program only gives 3 values and is missing one value. Can someone help me find out the issue in this code?

For input 1*0*, this solution only gives 3 results: 1000, 1001, 1101. The missing value is 1100. Thanks.

public class TestClass{
        public static void generateComb (char[] ch, int index) {
            if (index == ch.length)
            {
                System.out.println (ch);

                return;
            }
            if (ch[index]=='*'){

                ch[index] = '0';
                generateComb (ch, index+1);
                ch[index] = '1';

                generateComb (ch, index+1);                        
            }
            else {
                generateComb (ch, index+1);   
                
            }
        }
        
        public static void main (String[] args) throws Exception {
        
            char[] chtest = {'1', '*', '0', '*'};
            generateComb(chtest, 0);
        }
    }

score 0 · Accepted Answer · edited May 23 '17 at 12:23

What's happening here is that when you say ch[index] = '0'; you're changing that object, and you're not setting that character back to a *, therefore after the second * gets turned to a 1, it's no longer replaced. This is called pass by reference, char[] ch is a reference to the string. See this question for an example.

This should work:

public class TestClass{
        public static void generateComb (char[] ch, int index) {
            if (index == ch.length)
            {
                System.out.println (ch);

                return;
            }
            if (ch[index]=='*'){

                ch[index] = '0';
                generateComb (ch, index+1);
                ch[index] = '1';
                generateComb (ch, index+1);
                ch[index] = '*'; // <-------------- here
            }
            else {
                generateComb (ch, index+1);   
                
            }
        }
        
        public static void main (String[] args) throws Exception {
        
            char[] chtest = {'1', '*', '0', '*'};
            generateComb(chtest, 0);
        }
    }

An example of what's going on in each round might help:

ch = [1, *, 0, *], index == 0
ch = [1, *, 0, *], index == 1 ch[1] changed to '0'
ch = [1, 0, 0, *], index == 2
ch = [1, 0, 0, *], index == 3 ch[3] changed to '0'
ch = [1, 0, 0, 0], index == 4 prints: 1000 returns to prior call and ch[3] is changed to '1'
ch = [1, 0, 0, 1], index == 4 prints: 1001 returns up the call stack, ch[1] is changed to '1'
ch = [1, 1, 0, 1], index == 2
ch = [1, 1, 0, 1], index == 3
ch = [1, 1, 0, 1], index == 4 prints: 1101

Using a debugger to step through this might help further show the problem

Thanks a lot! This is exactly the gap what I'm missing. – John Da Dec 07 '15 at 05:03 — John Da, Dec 07 '15 at 05:03

Pattern Generation Recursion

1 Answers1