Low-complexity computation of all binary vectors of length n, sorted by weight

Question

I use the following function in MATLAB to compute all binary vectors of length n in ascending order in log(2^n) steps.(All binary numbers of length n).

A = compV([0;1],n);

function [O] = compV(O,n)

            j = length(O);

            if n > 1
                O1 = [zeros(j,1) O];
                O2 = [ones(j,1) O];
                O = [O1;O2];
                O = compV(O,n-1);
            end
end

I want to find an algorithm that computes recursively the same vectors but sorted by weight. And all that in relatively low complexity.

For example: 000 001 010 011 100 101 110 111 -> 000 001 010 100 011 101 110 111

I have run out of ideas and i am not sure if this can be done at all.

Thanks!

Answer 1

My interpretation of the question is: you would like the binary representation of the numbers from 0:2^n-1. You're trying to do it recursively because some people love recursion. I know my solution isn't recursive, but that seems like a bad idea given the exponential nature of the problem.

Try dec2bin(0:2^n-1)-'0'. dec2bin converts the number to a binary string representation. Subtracting '0' converts the binary string to a double array (the format your code is producing).

Notes: I'm not sure what you mean by log(2^n) steps. Don't know what you mean by sorted by weight -- by increasing value?

Edit: It has been clarified that you would like the integers to be sorted by lowest to highest Hamming weight. This answer explains how to find the next number with a given Hamming weight. You can go through the Hamming weights i=0:n enumerating all of the numbers with a given weight. Start with the smallest number for a given weight: n-i 0s followed by i 1s. Using the linked algorithm, you can find the next number with the same Hamming weight, until the number of bits required is greater than n.