All possible combinations given a binary number

[LeanA]

Hi all,

I have a 2D array which represents the binary numbers.

Given a 2D array of [count][posvalues], count refers to the number of binary, and posvalues refer to the possible values of each binary.

Ex. binary num: [0, 1] [0,1] [0,1]

Count = 3
Possible Values = 2 (given by 0 and 1)

I want to find all the possible combinations of everything in the array using a Recursive solution, but I'm having a hard time.

Please help me, it's driving me crazy!

Thank you!

[JosAH]

Hi all,

I have a 2D array which represents the binary numbers.

Given a 2D array of [count][posvalues], count refers to the number of binary, and posvalues refer to the possible values of each binary.

Ex. binary num: [0, 1] [0,1] [0,1]

Count = 3
Possible Values = 2 (given by 0 and 1)

I want to find all the possible combinations of everything in the array using a Recursive solution, but I'm having a hard time.

Please help me, it's driving me crazy!

Thank you!

If you want to find all possible combinations of 'n' bits, you just have to count in binary; e.g. for n == 3 you have the combinations 000, 001, 010, 011, 100, 101, 110 and 111 (eight combinations). In general there are 2^n combinations (^ == power of).

kind regards,

Jos

[LeanA]

Hi JosAH, thanks for replying.

Thank you for that, although to confirm, I am looking for the 000, 001, 010, ..., etc. I want to print those possible combinations.

Thank you again.

[JosAH]

Hi JosAH, thanks for replying.

Thank you for that, although to confirm, I am looking for the 000, 001, 010, ..., etc. I want to print those possible combinations.

Thank you again.

If n == 3 there are eight possible combinations; do you want them all or just a particular selection from all combinations?

kind regards,

Jos

[LeanA]

Hi JosAH, thanks again for replying.

Yes, I want them all. For example, I have count == 3;

Then my wanted output would be:

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

I am having a hard time implementing it on the 2D array specified above. The reason that I am using a 2D array is because the values may not just be (0 and 1). It can have 2 values. For example: n = 2, and possible values = 0, 1, 2

0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

Or something like that.

Thanks again.

[JosAH]

It's still just counting given a certain radix; e.g. suppose you have the number 012 and the allowed values are 0, 1, and 2; you start from the right and check if the digit < 2; if not reset the digit and move to the left; if so, increment the digit and stop; so 012 --> 020. The following example illustrates the algorithm:

import java.util.Arrays;

public class Combination {

	public static int[] next(int[] current, int radix) {
		int[] n= new int[current.length];
		
		for (int i= n.length; i-- > 0;) {
			if (current[i]+1 == radix)
				n[i]= 0;
			else {
 				n[i]= current[i]+1;
 				for (; i-- > 0; n[i]= current[i]);
 				return n;
			}
		}
		return null;
	}
	
	public static void main(String[] args) {
		
		int N= 4, M= 3; // values 0, 1, 2, 3 (<N), we want M=3 of them
	
		int[] a= new int[M];
		
		do {
			System.out.println(Arrays.toString(a));
		}
		while ((a= next(a, N)) != null);
	}
}

kind regards,

Jos

[Zack]

Crap, someone beat me to it. I have a bit of semi-pseudocode that I threw together using Python as a test base that you might find helpful. Just putting this here so that my staying up till 1:30am wasn't in vain!

public void printcombos(int n, int[] posvalues, int base, int[] values) {
	// N is your count;
	// Posvalues is an int array of possible values;
	// Base is the base counter for the posvalues index to display; start this at zero;
	// Values is an array of values to display; start this as blank {}.
	for (int i = 0; i < posvalues.length; i++) {
		newvals = arraycopy(values);
		newvals.push(posvalues[i]);
		if (base <= len(posvalues)) {
			printcombos(n,posvalues,base + 1,newvals);
		}
		if (newvals.length == n) {
			System.out.println(Array.toString(newvals));
		}
	}
}

// Call this function using:
//	printcombos(2,{0,1,2},0,{});

Best of luck to you!

(PS: That's quite a bit of code, Jos. Top marks. Not sure that the do/while counts as recursion, though...)

[JosAH]

(PS: That's quite a bit of code, Jos. Top marks. Not sure that the do/while counts as recursion, though...)

Nah, you don't need recursion if you want to generate all combinations given a set size N and an alphabet size M. Counting them iteratively will do fine ...

kind regards,

Jos

[LeanA]

Hi JosAH and Zack,

Thank you for those code. Although a little different from what I am aiming for, I think that I can try to modify those.

What I really am aiming for is something like this (inputting the 2D array to the function):

public static void PrintPossibleKeys(String[][] possiblecombo)
{

     //Recursively iterate through the 2D array then print every possible     combination
}

Thank you very much for your help!

[LeanA]

Hi all,

I finally solved this problem. Here is the recursive printing of the values:

public static void PrintPossibleKeys(String[][] possibledecrypted, int i, int j, int max, int index, String curstring)
    {
        if((i+1) == max)
        {
            for(int c = 0; c < index; c++)
            {
                System.out.println("Test: " + curstring + " " + possibledecrypted[i][c]);
            }
        }
        else
        {
            for(int b = 0; b < index; b++)
            {
                PrintPossibleKeys(possibledecrypted, (i+1), 0, max, index, (curstring) + " " + possibledecrypted[i][b]);
            }
        }
 
    }

The main idea I used is to collectively collect the strings traversed and pass it as a parameter then print everything out once it reaches the final.

Thank you all!