Results 1 to 10 of 10
  1. #1
    LeanA is offline Member
    Join Date
    Jun 2010
    Posts
    5
    Rep Power
    0

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

    Please help me, it's driving me crazy!

    Thank you!

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,431
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by LeanA View Post
    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

  3. #3
    LeanA is offline Member
    Join Date
    Jun 2010
    Posts
    5
    Rep Power
    0

    Default

    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.

  4. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,431
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by LeanA View Post
    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

  5. #5
    LeanA is offline Member
    Join Date
    Jun 2010
    Posts
    5
    Rep Power
    0

    Default

    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. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,431
    Blog Entries
    7
    Rep Power
    20

    Default

    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;) {
    			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

  7. #7
    Zack's Avatar
    Zack is offline Senior Member
    Join Date
    Jun 2010
    Location
    Destiny Islands
    Posts
    692
    Rep Power
    5

    Default

    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) {
    	// 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...)
    Last edited by Zack; 06-18-2010 at 08:58 AM. Reason: Added my PS! ;)

  8. #8
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,431
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Zack View Post
    (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. #9
    LeanA is offline Member
    Join Date
    Jun 2010
    Posts
    5
    Rep Power
    0

    Default

    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. #10
    LeanA is offline Member
    Join Date
    Jun 2010
    Posts
    5
    Rep Power
    0

    Default

    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!

Similar Threads

  1. Finding a number in array close to another number
    By SteroidalPsycho in forum New To Java
    Replies: 2
    Last Post: 02-15-2010, 12:37 AM
  2. Printing the Number of Times a Number in a Range Shows up
    By space4rent00 in forum New To Java
    Replies: 1
    Last Post: 02-05-2010, 10:42 PM
  3. Replies: 1
    Last Post: 08-07-2009, 12:14 PM
  4. Replies: 1
    Last Post: 11-03-2008, 02:38 PM
  5. Converts a binary number to a decimal
    By cachi in forum New To Java
    Replies: 1
    Last Post: 08-01-2007, 09:57 AM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •