Print all permutations with some constraints I've the following problem:


  Print all valid phone numbers of length n subject to following
  constraints: 
       1.If a number contains a 4, it should start with 4 
       2.No two consecutive digits can be same 
       3.Three digits (e.g. 7,2,9) will be entirely disallowed, take as input


Here's my solution:

public static void ans(int length, int d1, int d2, int d3) {
    StringBuffer numbers = new StringBuffer();

    for(int i = 0; i &lt; 10 ;i++) {
        if(i != d1 &amp;&amp; i != d2 &amp;&amp; i != d3) {
            numbers.append(i);
        }
    }
    printNumbers("", numbers.toString(), length);
}

public static void printNumbers(String soFar, String remaining, int length) {
    if(soFar.length() == length) {
        boolean four = false;
        boolean sameAdjDigits = false;

        for(int i = 1; i &lt; soFar.length(); i++) {
            if(soFar.charAt(i-1) == soFar.charAt(i)) sameAdjDigits = true;
            if(soFar.charAt(i) == '4') four = true;
        }

        if(!sameAdjDigits) {
            if(!four || (four &amp;&amp; soFar.charAt(0) == '4'))
                System.out.print(soFar + " ");
        }

        return;
    }

    if(soFar.length() &lt; length) {
        for(int i = 0; i &lt; remaining.length(); i++) {
            String newSoFar = soFar + remaining.charAt(i);
            String newRemaining = remaining.substring(0, i) + remaining.substring(i+1);
            printNumbers(newSoFar, newRemaining, length);
        }
    }
}


I ran some tests on this code and checked all the printed values. It worked for length 1 and 2. However, I couldn't verify for length > 2 because there were too many numbers.

Can anyone verify if my code runs a correct result? Is there any part of the code that can be improved?
Nitpicks

public static void ans(int length, int d1, int d2, int d3) {


Any time that I see numbered variables, I want to replace them with a collection.  Since we know that there will be no duplicate values, I'd use a Set.  

public static void generatePhoneNumbers(int length, Set&lt;Character&gt; disallowedDigits) {


Also, I find d an unclear name, so I switched to disallowedDigits which I find clearer.  

I switched from int to Character as you are building a string.  We could just as easily be working with the letters of the alphabet as with numeric digits.  

StringBuffer numbers = new StringBuffer();


This seems an ideal place to use a StringBuilder.

StringBuilder digits = new StringBuilder();


I also changed the name to digits, as that tells me that we're talking about one digit at a time rather than multi-digit numbers.  

            if(!four || (four &amp;&amp; soFar.charAt(0) == '4'))


You could just as well write 

            if( ! four || soFar.charAt(0) == '4' )


If the string begins with a 4, then we don't care if none of the rest have a 4.  

Fulfilling the Problem Statement

        String newRemaining = remaining.substring(0, i) + remaining.substring(i+1);


This is actively wrong given your problem statement:  


  Print all valid phone numbers of length n subject to following constraints:
  1.  If a number contains a 4, it should start with 4
  2.  No two consecutive digits can be same
  3.  Three digits (e.g. 7,2,9) will be entirely disallowed, take as input  


From #2, only consecutive digits can't be the same.  So you should not be removing digits from your remaining String.  Like length, that will be constant for all calls.  

We can rewrite #1 to say:  only numbers that start with 4 can contain 4.  This effectively gives us different rules for 4 than other values.  Since we're supposed to generate all numbers, I'd suggest that we generate all numbers starting with 4 separately from other numbers.  Fortunately, #3 means that we already need a way to exclude digits from the set.  

ans

Here's how I'd write the method that you called ans:  

private final static char [] DIGITS = "0123456789".toCharArray();

public static void generate(int length, Set&lt;Character&gt; disallowedDigits) {
    Set&lt;Character&gt; allowedDigits = new TreeSet&lt;Character&gt;();

    for ( Character digit : DIGITS ) {
        if ( ! disallowedDigits.contains(digit) ) {
            allowedDigits.add(digit);
        }
    }

    if ( allowedDigits.contains('4') ) {
        printNumbers("4", allowedDigits, length);
        allowedDigits.remove('4');
    }

    for ( Character digit : allowedDigits ) {
        printNumbers("" + digit, allowedDigits, length);
    }
}


First, we define a constant to hold the possible digit values.  Then we make a new Set that masks out the disallowedDigits.  If 4 is allowed, then we generate all the numbers that start with 4 separately.  Then we remove 4 from the allowedDigits, as it won't be allowed in any of the other numbers.  

printNumbers

    if(soFar.length() == length) {
        boolean four = false;
        boolean sameAdjDigits = false;

        for(int i = 1; i &lt; soFar.length(); i++) {
            if(soFar.charAt(i-1) == soFar.charAt(i)) sameAdjDigits = true;
            if(soFar.charAt(i) == '4') four = true;
        }

        if(!sameAdjDigits) {
            if(!four || (four &amp;&amp; soFar.charAt(0) == '4'))
                System.out.print(soFar + " ");
        }

        return;
    }


This whole section of code is unnecessary, except for one line (the print).  Instead of generating invalid strings and masking them out, just don't generate them in the first place.  That will save all subsequent recursive calls down that path.  

    if(soFar.length() &lt; length) {
        for(int i = 0; i &lt; allowedDigits.length(); i++) {
            String newSoFar = soFar + allowedDigits.charAt(i);
            String newRemaining = allowedDigits.substring(0, i) + allowedDigits.substring(i+1);
            printNumbers(newSoFar, newRemaining, length);
        }
    }


I switched to a Set to hold the digits that can be used, so this is going to be a bit different.  

private static void printNumbers(String soFar, Set&lt;Character&gt; allowedDigits, int length) {
    int lengthSoFar = soFar.length();

    if ( lengthSoFar &lt; length ) {
        Character last = soFar.charAt(lengthSoFar - 1);

        for ( Character digit : allowedDigits ) {
            if ( ! digit.equals(last) ) {
                printNumbers(soFar + digit, allowedDigits, length);
            }
        }
    } else {
        System.out.println(soFar);
    }
}


First, we already took care of 4 in our generate function.  Here, it will either be in allowedDigits or it won't.  

Second, we take care of the rule about consecutive digits by simply not starting the recursive generation in that case:  if ( ! digit.equals(last) ) {.

I put each number on its own line.  For all but trivial lengths, there are too many numbers to fit on a single line.  

Note that soFar is the only parameter that changes from call to call.  

Testing

This is a bit difficult.  Because we print the numbers to standard output, we can't run normal unit tests on them.  The simplest way to handle this is to direct the output to a file.  Then we can search the file for values that should or shouldn't be there.  

For example, we should never have any of the following sequences:  00, 11, 22, 33, 44, 55, 66, 77, 88, 99, 00.  So search for those in the file.  If they don't exist, then you know that rule is working.  

Search for lines containing the disallowedDigits.  There shouldn't be any. 

Find all the lines in the file that contain a 4 and verify that 4 is the first digit of the number.  On Linux, that might be written something like 

fgrep '4' &lt; phone_numbers.txt | cut -c1 | sort | uniq -c


If there are any values other than 4, then you can look them up more specifically.  

Also search for a few values that you construct, e.g. for a length of 8 where 7, 2, and 9 are disallowed, 40134568 should be in the list.  Also 86868686 should be there.