1

I want to find all possible binary permutations with a given number of ones in Java:

  • x is the desired number of ones in each sequence
  • n is the desired length of each sequence

For an example:

x=2, n=4

Output: 1100, 0011, 1010, 1001, 0101, 0110

I'm searching for an elegant and fast way to do this. Can you help me? I've tested eboix solution in Print list of binary permutations but it is unfortunately too slow because the algorithm in this example is searching for all 2^n binary permutations. I want to find sequences with a length of 50 or 100.

Community
  • 1
  • 1
  • This might help http://stackoverflow.com/questions/19676109/how-to-generate-all-the-permutations-of-a-multiset – beaker Jul 14 '15 at 15:48
  • You're looking for [combinations](https://en.wikipedia.org/wiki/Combination), not permutations. You want to take **n** things **k** at a time. If you want all of the 4-bit numbers that have 2 bits set, you want the combinations of 4 things taken 2 at a time. There is at least one Java combinatorics library that'll do it for you. – Jim Mischel Jul 15 '15 at 02:59
  • The problem is: I need "some" of the sequences with a 100 bit length and a given number of ones. Maybe I should create them on other ways, because there are too much of them with 100 bit length or more. I need only the not similar sequences. With not similar I mean sequences, who have a different number of runs. For an example: If x=2, n=100. I want to find one sequence with one runs: 1100000...., one with two runs 1010000.... If x=3, n = 100: I want to find one sequence with 1 runs: 1110000..., one with two runs 101100000.... and one with three runs 1010100000.... and so on. –  Jul 15 '15 at 10:59
  • @ Jim Mischel, I will take a look at the library, thank you. –  Jul 15 '15 at 11:07

4 Answers4

0

First of all, you're missing 0110 as an output case.

It's fairly intuitive that there are n choose x possibilities. You're finding all valid arrangements of x identical items among n total slots. So you can find the total number of sequences in O(1).

As a hint, try simply finding all permutations of the bitstring consisting of x ones followed n - x zeros.

To specifically address the problem, try creating a recursive algorithm that decides at every ith iteration to either include 1 or 0. If 1 is included, you need to decrement the count of 1's available for the rest of the string.

Aaron Zou
  • 414
  • 3
  • 9
0

Actually, there may be an elegant way, but no fast way to do this. The number of string permutations is given by the binomial coefficient (see https://en.wikipedia.org/wiki/Binomial_coefficient). For example, x=10, n= 50 gives over 10 million different strings.

DubioserKerl
  • 82
  • 5
0

Here is just a basic version that will generate your desired output. Please work on it to make it more accurate/efficient -

This will not generate all the combinations, but you will get the idea of how to do it. Off course, for all the possible combinations generated by this, you will have to generate all the other possible combinations.

public class Test {
    static int iter = 0;
    public static void main(String args[]){
        int n = 50;
        int x = 5;
        byte[] perms = new byte[n];
        for(int i=0; i<x; i++){
            perms[i] = 1;
        }
        print(perms);
        for(int j=x-1; j>=0; j--){
            for(int i=1; i<(n/2-j); i++){
                iter++;
                swap(perms, j, i);
            }
        }
    }
    public static void swap(byte[] perms, int pos, int by){
        byte val = perms[pos+by];
        perms[pos+by] = perms[pos];
        perms[pos] = val;
        print(perms);
        val = perms[pos+by];
        perms[pos+by] = perms[pos];
        perms[pos] = val;
    }

    public static void print(byte[] perms){
        System.out.println("iter = "+iter);
        for(int i=0; i<perms.length; i++){
            System.out.print(perms[i]);
        }
        System.out.println();
        for(int i=perms.length-1; i>=0; i--){
            System.out.print(perms[i]);
        }
        System.out.println();
    }
}
zookastos
  • 917
  • 10
  • 37
  • I will try to post the fully working recursive code, as and when I will get some time to work on this. -Thanks. – zookastos Jul 13 '15 at 21:00
0

Another inspiration for you. A dirty version which works. It allocates extra array space (you should adjust size) and uses String Set at the end to remove duplicates.

public static void main(String[] args) {
    int x = 2;
    int n = 4;

    Set<BigInteger> result = new LinkedHashSet<>();
    for (int j = x; j > 0; j--) {
        Set<BigInteger> a = new LinkedHashSet<>();

        for (int i = 0; i < n - j + 1; i++) {
            if (j == x) {
                a.add(BigInteger.ZERO.flipBit(i));
            } else {
                for (BigInteger num : result) {
                    if (num != null && !num.testBit(i) && (i >= (n - j) || num.getLowestSetBit() >= i-1))
                        a.add(num.setBit(i));
                }
            }
        }
        result = a;
    }

    String zeros = new String(new char[n]).replace("\0", "0");
    for (BigInteger i : result) {
        String binary = i.toString(2);
        System.out.println(zeros.substring(0, n - binary.length()) + binary);
    }

}

EDIT: changed the primitives version to use BigInteger instead to support larger n,x values.

Ilya Novoseltsev
  • 1,803
  • 13
  • 19
  • A perfect size formula is `size = size * (n + 1 - x);`. Enjoy! – Ilya Novoseltsev Jul 13 '15 at 21:53
  • I've changed the initial algorithm - no more maps or sets, only pure int[] performance! – Ilya Novoseltsev Jul 14 '15 at 07:54
  • Thanks for posting! This code seems to be working with any x and n values under 32. But if n = 33 or bigger, the output goes wrong. For an example n=33, x=1, the last output is not the desired 10000..... –  Jul 14 '15 at 10:08
  • Fixed that - it now takes long and should work for n up to 64. If you need more, it will take some more effort. – Ilya Novoseltsev Jul 14 '15 at 22:23
  • Thank you very much! Yes - now it works with n values under 65, but with x values over 1, you will get an java.lang.ArrayIndexOutOfBoundsException in line " a[pos++] = num | (long) 1 << i;". I will create a new post in a few moments here, to explain my problem. Maybe this is not the right way, because there a too much sequences.... –  Jul 15 '15 at 10:58
  • Ok, if you need n>100 then BigInteger is the only choice left. I modified my answer above, feel free to test it. – Ilya Novoseltsev Jul 18 '15 at 12:30