Monday, April 26, 2010

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)

0 comments:

Post a Comment