# Thread: All possible combinations given a binary number

1. Member
Join Date
Jun 2010
Posts
5
Rep Power
0

## All possible combinations given a binary number

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.

Thank you!

2. Originally Posted by 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.

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

3. Member
Join Date
Jun 2010
Posts
5
Rep Power
0

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.

4. Originally Posted by LeanA

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

5. Member
Join Date
Jun 2010
Posts
5
Rep Power
0
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.
Last edited by LeanA; 06-18-2010 at 07:55 AM.

6. 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:

Java Code:
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;) {
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

7. 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!

Java Code:
public void printcombos(int n, int[] posvalues, int base, int[] values) {
// 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...)
Last edited by Zack; 06-18-2010 at 08:58 AM. Reason: Added my PS! ;)

8. Originally Posted by Zack
(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

9. Member
Join Date
Jun 2010
Posts
5
Rep Power
0
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):

Java Code:
public static void PrintPossibleKeys(String[][] possiblecombo)
{

//Recursively iterate through the 2D array then print every possible     combination
}
Thank you very much for your help!

10. Member
Join Date
Jun 2010
Posts
5
Rep Power
0
Hi all,

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

Java Code:
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!