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.

Ashton
  • 119
  • 3
  • 4
  • 14
  • 1
    Check the first answer to this question: http://stackoverflow.com/questions/8461438/print-list-of-binary-permutations. Instead of System.out.println, save it to a list – Evans Oct 28 '13 at 00: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. – Radiodef Oct 28 '13 at 00: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)](http://docs.oracle.com/javase/6/docs/api/java/lang/Integer.html#toBinaryString(int)) to get the values. Is there a particular reason why you're going through such convolutions to do this? –  Oct 28 '13 at 00: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. – Ashton Oct 28 '13 at 01: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 – Ashton Oct 28 '13 at 01:04

2 Answers2

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
Radiodef
  • 37,180
  • 14
  • 90
  • 125
  • Thank you so much for detailing this so well. Can you explain this line: n.append(((list.size() >> i) & 1 == 1) ? 1 : 0); Thanks – Ashton Oct 28 '13 at 01:20
  • 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. – Radiodef Oct 28 '13 at 01:22
  • I know your code works. I just wanted to understand it all. :) – Ashton Oct 28 '13 at 01:24
  • 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: http://en.wikipedia.org/wiki/Bitwise_operation#AND – Radiodef Oct 28 '13 at 01:30
  • I get the bitwise AND and the ternary operator, but I don't really understand the shift >> operator. – Ashton Oct 28 '13 at 01:38
  • 1
    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"; }`. – Radiodef Oct 28 '13 at 01:39
  • so what does the shift operator do? where you go list.size()>>i Can you just use assignment for that or does it have to be the shift? – Ashton Oct 28 '13 at 01:43
  • The shift simply shifts the bit pattern to the left or right. `1 << 2 = 4` because `001 << 2 = 100`. Mathematically `x << n` is basically equivalent to saying `x * 2 ^ n` and `x >> n` is basically equivalent to `x / 2 ^ n`. There is some nuance with negative numbers because Java has both a signed and unsigned right shift, >> and >>> respectively. >> keeps the signage and >>> ignores the signage and shifts the whole bit pattern. The combination of the >> and the &, `(n >> 2) & 1` tells you whether bit #3 is a 1 or 0. – Radiodef Oct 28 '13 at 01:46
  • Just curious, if I wanted to expand this to a larger scale, how would I be able to do that? The method stops working at 11. – Ashton Oct 28 '13 at 01:51
  • You mean bits == 11? That's probably because it's trying to list a very large 2^n value. I suppose you could do the listing at large word lengths but it will take some time and you probably shouldn't try to print the list. – Radiodef Oct 28 '13 at 01:55
  • I see, yeah you're right, I tried running it and get a stack overflow at 14 bits. I don't know! I get the overflow at String in StringBuilder.toString(). Apparently it is too much for Java to handle. I tried increasing the memory but that didn't work (and shouldn't matter at such a relatively small value). – Radiodef Oct 28 '13 at 02:10
  • I can squeeze out an extra bit by adding the following line to the method: `if (list.size() % 100 == 0) System.gc();` which prompts garbage collection to clear old objects on every 100th iteration but it still fails at 15 bits. So it seems like it just has a limitation of sorts. It's possible this could go higher without the recursion, I don't know. – Radiodef Oct 28 '13 at 02:20
  • No problem. I fiddled around with it and I'm just not really sure how to expand it with the recursion. The basic problem is (I assume) that because the recursive call is inside the method, the prior methods never return until the very last one does. That means that all the method calls are "kept alive" simultaneously and likewise any objects created inside them. This is just in the nature of it being recursive and there's not much you can do about it to solve it completely. – Radiodef Oct 28 '13 at 02:59
  • Actually here is a SO question that has some answers on the topic: http://stackoverflow.com/questions/860550/stack-overflows-from-deep-recursion-in-java Though the fundamental problem still remains, that recursion is going to be more intensive than iteration (loops) in Java. So what you can do is increase the stack size by running the application with the modifier `-Xss(some number)m` where some number is size in MB, eg `-Xss500m`. But as some of the answers there say this is not necessarily a good thing to be doing. – Radiodef Oct 28 '13 at 03:11
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.

sdanzig
  • 4,510
  • 1
  • 23
  • 27
  • 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. – Ashton Oct 28 '13 at 01:06
  • Yeah, I could have modified this to use ints rather than strings, but I'm sure Radiodef's got it covered :) – sdanzig Oct 28 '13 at 01:29