Permutations of 1s and 0s

Question

I need an efficient way to permute a given numbers of 1s and 0s in a string with a specified string length. For example, if there is a string that is 6 numbers long, and it has only one 1 in it, then all permutations of that string would be:

000001
000010
000100
001000
010000
100000

The main concern with the method I need is that it should not run through 6! different permutations that are the same as each other. In other words, it should not permute indistinguishable zeroes with one another and only permute the distinguishable characters.
Is there way of implementing this is in Java? And thank you in advance :)

Came here expecting @RobbyCornelissen's answer.. was not disappointed.. — Sid, Aug 14 '15 at 02:41
The answer to your question will probably involve determining _all_ binary representations of the numbers 1 through 32, then filtering out binary values which do not match your desired number of 1's. This is a lengthy answer and you did not show us any effort. — Tim Biegeleisen, Aug 14 '15 at 02:42
Sorry, and how would it be implemented in java? @TimBiegeleisen — Chromatica, Aug 14 '15 at 02:52
In general, you should do research and then ask a specific question here. If you're looking for how many ways you can permute n 1's with m 0's, that's the same as placing n identical objects in (n+m) holes. You'll need to do some searching for algorithms. — Erwin Bolwidt, Aug 14 '15 at 02:54
@Chromatica Stack Overflow isn't really a code writing service. That being said, have a look at [this great SO post](http://stackoverflow.com/questions/4421400/how-to-get-0-padded-binary-representation-of-an-integer-in-java). It will get you started. The rest is just implementation. — Tim Biegeleisen, Aug 14 '15 at 02:55

score 4 · Accepted Answer · edited May 23 '17 at 12:22

A couple of approaches occur to me off the top of my head.

Approach 1. Generate all permutations of the string (using, say, the method in this answer). Throw them all into a Set and voilà, you eliminate the duplicates.

Approach 2. Count the number of ones. Then generate all permutations by distributing the ones at all combinations of positions. (Note that the initial positions of the ones is irrelevant to the result.) A recursive method might be something like this:

public List<String> generatePermutations(int numOnes, int stringLength) {
    final StringBuilder sb = new StringBuilder();
    final List<String> result = new ArrayList<>();
    distributeOnes(numOnes, stringLength, sb, result);
    return result;
}

private void distributeOnes(int numOfOnesRemaining, int positionsToFill, StringBuilder sb,
    List<String> result)
{
    if (numOfOnesRemaining == 0) {
        while (positionsToFill-- > 0) {
            sb.append('0');
        }
        result.add(sb.toString());
        return;
    }
    final int lastPos = positionsToFill - numOfOnesRemaining;
    final int sbLength = sb.length();
    for (int i = 0; i <= lastPos; ++i) {
        // put i zeros
        for (int j = 0; j < i; ++j) {
            sb.append('0');
        }
        // put in the next one
        sb.append('1');
        // recurse with one less one and i+1 fewer positions to fill
        distributeOnes(numOfOnesRemaining - 1, positionsToFill - i - 1, sb, result);
        // undo the changes that we made to sb
        sb.setLength(sbLength);
    }
}

The distributeOnes() method could be improved a bit. There's no need to append i zeros each time through the loop; we should be able to reorganize the code to only append a single zero each time through. However, that would involve different bookkeeping (including different logic for resetting the length of sb) and I'm too lazy to work it out :-)

KimvdLinde · Answer 2 · 2015-08-14T05:10:47.010

There are several options to solve this.

Use a bit shift operator. Start with one (000001, do the thing you need to do. Then bit shift it left (<<) one position and you get 000010. etc.
Use a power series. Math.pow(2,x) will give you the series you are looking for.

You can then use the bit values to generate the permutations in the String.

EDIT: recursive method:

public final class Permutator {

  public static void main(String[] args) {
    new Permutator(3, 6);
  }

  public Permutator(int numberOfOnes, int length) {
    StringBuilder start = new StringBuilder();
    for (int x = 0; x < length; x++)
      start.append('0');
    permutate(numberOfOnes, 0, 0, length, start);
    System.exit(0);
  }

  public void permutate(int numberOfOnes, int first, int depth, int length, StringBuilder base) {
    for (int x = first; x < length; x++) {
      StringBuilder onesAndZeros = new StringBuilder(base.toString());
      onesAndZeros.setCharAt(x, '1');
      if (numberOfOnes == depth + 1)
        System.out.println(onesAndZeros.toString());
      else
        permutate(numberOfOnes, x + 1, depth + 1, length, onesAndZeros);
    }
  }
}

Outcome for new Permutator(1, 6):

for new Permutator(2, 6):

for new Permutator(4, 6):

Yeah, but that only deals with the case where there's one `1`. The question states: *permute a given numbers of 1s and 0s*. — Robby Cornelissen, Aug 14 '15 at 02:45
This will not generate all permutations; only the cyclic permutations. — Ted Hopp, Aug 14 '15 at 02:45

Permutations of 1s and 0s

2 Answers2