# All possible combinations given a binary number

• 06-18-2010, 07:30 AM
LeanA
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!
• 06-18-2010, 07:41 AM
JosAH
Quote:

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
• 06-18-2010, 07:43 AM
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.
• 06-18-2010, 07:48 AM
JosAH
Quote:

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
• 06-18-2010, 07:52 AM
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.
• 06-18-2010, 08:19 AM
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:

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;) {                         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
• 06-18-2010, 08:57 AM
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!

Code:

```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...)
• 06-18-2010, 09:04 AM
JosAH
Quote:

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
• 06-18-2010, 09:16 AM
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):

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!
• 06-18-2010, 05:33 PM
LeanA
Hi all,

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

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!