Thursday, September 25, 2008

print combinations

All possible combinations of a 3 digit binary number are 2c1 * 2c1 * 2c1 = 8 (000, 001, 010, 011, 100, 101, 110, 111). Each digit can be 0 or 1 so 2c1. Below is the code for it.

Starting with 000, we get the next combination by incrementing the LSbs and carrying out the ripple effect with the for loop.

void printCombinations(int digits):
    char[] out = new char[digits]

    for (int i = 0; i < out.length; i++):
        out[i] = '0'

    while (true):
        print(out)
        
        int i 
        for(i = out.length -1; i >= 0; i--):
            if (out[i] == '0'):
                out[i] = '1'
            else if (out[i] == '1'): 
                out[i] = '0'
                continue
            break
        
        if (i == -1):
            break

If each digit can have more values (for decimal 0 to 9, or characters A B C ... Z), the if-else would change (better with a mapping function). There is a (intuitive, simple) recursive solution too but recursion is a overhead for large combinations.

printCombinations_Recursive (char[] out, int index): 
    if (index == out.length): 
        print(out)
        return
    
    for (int bit = 0; bit <= 1; bit++):
        out[index] = bit //(char) (bit +'0') or a mapping function
        printCombinations_Recursive(out, index + 1)

printRecursiveWrapper (int digits):
    char[] out = new char[digits]
    printCombinations_Recursive(out, 0)


[Hat tip to PIE]

No comments:

Post a Comment