1

I want to find the 2^n permutations of any size based on user input. I have no idea how to do this. I know that I have to use recursion. Unlike most examples I've seen, the parameter of the function is only the number input, there is no string that can be used to make all the permutations. All the permutations are to be stored in an arrayList and output to the user. i.e (input 3) output: 000 001 010 011 100 101 110 111 Here's the code I have so far:

public static void printBin(int bits) {
    ArrayList<String> binaryArray = new ArrayList<String>();

    if(bits == 0) {
        System.out.println(binaryArray);
    }
    else {
        for (String string2 : binaryArray) {
            String comp = "";
            if (comp.length() <= string2.length()) {
                comp = string2;
                string = comp;
            }
            string.concat("0");
            binaryArray.add(string);
            printBin(bits - 1);
            string.concat("1");
            binaryArray.add(string);
            printBin(bits-1);
        }


    }
}

Thanks in advance.

Improve this question
5
  • 1
    Check the first answer to this question: stackoverflow.com/questions/8461438/…. Instead of System.out.println, save it to a list Commented Oct 28, 2013 at 0:55
  • You don't have to use recursion, you could just do this in a for loop. Is disallowing the current iteration as a parameter required? I assume what you are doing is to add each number to the list. If you can't make a parameter for the current number to be added you will have to use the list size to find out what the current iteration is. Commented Oct 28, 2013 at 0:55
  • Do note that the values 000, 001, 010, 011, 100, 110, and 111 are the binary values of the numbers 0 .. 7. One could use Integer.toBinaryString(int i) to get the values. Is there a particular reason why you're going through such convolutions to do this? Commented Oct 28, 2013 at 0:56
  • I wish I didn't have to use recursion @Radiodef. haha I'm trying to wrap my head around recursion and this is the "homework" problem given in the book I have. I want to learn how to do it and understand it. Thanks anyway. Commented Oct 28, 2013 at 1:01
  • @Evans. Can you explain how to do the answer you suggested without using a String param. I'm not certain how to completely flip it around. Thanks Commented Oct 28, 2013 at 1:04

2 Answers 2

Reset to default
1

Well here is the best you can do I think.

import java.util.ArrayList;

public class BinaryList {

    public static void main(String[] args) {
        try {
            if (args.length != 1 || Integer.parseInt(args[0]) < 1)) {
                System.err.println("Invalid integer argument");
                return;
            }

            binaryRecursive(Integer.parseInt(args[0]), new ArrayList<String>(0));

        } catch (NumberFormatException e) {
            System.err.println("Argument not an integer");
        }
    }

    public static void binaryRecursive(int bits, ArrayList<String> list) {

        if (list.size() == (int)Math.pow(2, bits)) {
            for (String n : list) {
                System.out.println(n);
            }

        } else {
            StringBuilder n = new StringBuilder(bits);

            for (int i = bits - 1; i >= 0; i--) {
                n.append((list.size() >> i) & 1);
            }

            list.add(n.toString());

            binaryRecursive(bits, list);
        }
    }
}

There's no way to keep a list of them without either passing the last as a parameter, returning a value or keeping the list as a field.

Following the logic through for bits == 2 what you get is this:

* 1st method call

list.size() == 0

for 1 to 0 {
    (00 >> 1 = 00) & 01 == 0
    (00 >> 0 = 00) & 01 == 0
}

list.add("00")

* 2nd method call

list.size() == 1

for 1 to 0 {
    (01 >> 1 = 00) & 01 == 0
    (01 >> 0 = 01) & 01 == 1
}

list.add("01")

* 3rd method call

list.size() == 2

for 1 to 0 {
    (10 >> 1 = 01) & 01 == 1
    (10 >> 0 = 10) & 01 == 0
}

list.add("10")

* 4th method call

list.size() == 3

for 1 to 0 {
    (11 >> 1 = 01) & 01 == 1
    (11 >> 0 = 11) & 01 == 1
}

list.add("11")

* 5th method call

list.size() == 4 == 2 ^ 2

print the list
Improve this answer
Sign up to request clarification or add additional context in comments.

14 Comments

Thank you so much for detailing this so well. Can you explain this line: n.append(((list.size() >> i) & 1 == 1) ? 1 : 0); Thanks
The list size will innately be the next number to find. The bit shifting/masking is a way to determine the value of each bit.
I know your code works. I just wanted to understand it all. :)
I added a walkthrough showing the logic. If you're unfamiliar with the bitwise/bit shift stuff here is the Wikipedia article which explains them: en.wikipedia.org/wiki/Bitwise_operation#AND
Oh and the ? : syntax is an inline if/else if that is something you haven't seen before. It lets you do something like int n = 1; String s = n == 1 ? "1" : "0"; which is equivalent to int n = 1; String s; if (n == 1) { s = "1"; } else { s = "0"; }.
|
0

You start out with n.. I want n=3 bits. Your main function calls a function, "genBin", passing one arguments of ("0", n-1) and the other a ("1",n-1). genBin returns a List. The main function merges the two lists as one ArrayList.

genBin(String in, int bitsLeft), if bitsLeft > 0, calls itself with ("0"+in,bitsLeft-1) and ("1"+in,bitsLeft-1) and merges the two return values as an ArrayList. If bitsLeft == 0, it returns in as a single element ArrayList.

Your main function, upon doing that merge I previously mentioned, ends up with a merged List of all the permutations.

Improve this answer

2 Comments

I like your method @sdanzig but I need to do it without having a String parameter, only the integer value and I need an ArrayList instead of just output of multiple Strings. I can't seem to figure out how to tweak this method into working without using a String parameter, maybe you can shed some insight? Thanks.
Yeah, I could have modified this to use ints rather than strings, but I'm sure Radiodef's got it covered :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.