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 < 10 ;i++) {
        if(i != d1 && i != d2 && 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 < 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 && soFar.charAt(0) == '4'))
                System.out.print(soFar + " ");
        }

        return;
    }

    if(soFar.length() < length) {
        for(int i = 0; i < 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 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 && 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 disallowedDigits) {
    Set allowedDigits = new TreeSet();

    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 < 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 && 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() < length) {
        for(int i = 0; i < 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 allowedDigits, int length) {
    int lengthSoFar = soFar.length();

    if ( lengthSoFar < 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

StackExchange Code Review Q#74899, answer score: 8