Permutations of 0s and 1s with Recursion

I am trying to write all the 6-bit permutations of 0s and 1s using recursion (i.e., [0 0 0 0 0 1], [0 0 0 0 1 0], [0 0 0 0 1 1], [0 0 0 1 0 0], ... [1 1 1 1 1 1]). I'm following a tip I got from Yahoo! Answers I've got the following but it just doesn't go all the way to the end and there are duplicate entries.

function [c] = myIEEEBaby_all_decimals(h, n)

% n: number of characters more to add

if n == 0
   converter(h);
   return 
end

in1 = [h 1];
in2 = [h 0];

converter(in1);
converter(in2);

if length(h)开发者_如何学JAVA < n
    myIEEEBaby_all_decimals([in1], n-1)
    myIEEEBaby_all_decimals([in2], n-1)
end

end

function [d] = converter(IEEE)
% convert custom IEEE representation to decimal

IEEE = [zeros(1,6-length(IEEE)), IEEE];

s = IEEE(1);

characteristic = IEEE([2,3]);
k = find(fliplr(characteristic)) - 1;
c = sum(2.^k);

fraction = IEEE([4:6]);
f = sum(2.^-(find(fliplr(fraction))));

d = (-1)^s*2^(c-1)*(1+f);

disp([num2str(IEEE),' : ', num2str(d)]);

end

The output (MATLAB) is just:

>> myIEEEBaby_all_decimals([],6)
0  0  0  0  0  1 : 0.75
0  0  0  0  0  0 : 0.5
0  0  0  0  1  1 : 0.875
0  0  0  0  1  0 : 0.625
0  0  0  1  1  1 : 0.9375
0  0  0  1  1  0 : 0.6875
0  0  1  1  1  1 : 1.875
0  0  1  1  1  0 : 1.375
0  0  1  1  0  1 : 1.625
0  0  1  1  0  0 : 1.125
0  0  0  1  0  1 : 0.8125
0  0  0  1  0  0 : 0.5625
0  0  1  0  1  1 : 1.75
0  0  1  0  1  0 : 1.25
0  0  1  0  0  1 : 1.5
0  0  1  0  0  0 : 1
0  0  0  0  0  1 : 0.75
0  0  0  0  0  0 : 0.5
0  0  0  0  1  1 : 0.875
0  0  0  0  1  0 : 0.625
0  0  0  1  1  1 : 0.9375
0  0  0  1  1  0 : 0.6875
0  0  0  1  0  1 : 0.8125
0  0  0  1  0  0 : 0.5625
0  0  0  0  0  1 : 0.75
0  0  0  0  0  0 : 0.5
0  0  0  0  1  1 : 0.875
0  0  0  0  1  0 : 0.625
0  0  0  0  0  1 : 0.75
0  0  0  0  0  0 : 0.5

Simply iterate from 0 to 2⁶-1 and call Matlab's dec2bin(...) function. You could pad the result with zero's using sprintf(...).

If you want to compute every possible value of a 6-bit number, there are much more efficient ways to do it than using recursion. Using the function DEC2BIN is one option, but this previous question shows that implementations using the function BITGET or indexing via a look-up table are much faster. For example, here's one possible solution:

allperms = cell2mat(arrayfun(@(b) {bitget((0:2^6-1).',b)},6:-1:1));

Then you can apply your converter function to the result on a row-wise basis:

converter = @(b) (1-2.*b(:,1)).*...             %# The sign contribution
            2.^(b(:,2:3)*[2; 1] - 1).*...       %# The exponent contribution
            (1 + b(:,4:6)*[0.125; 0.25; 0.5]);  %# The fraction contribution
values = converter(allperms);

And you can display the results as follows:

>> disp(sprintf('%d %d %d %d %d %d : %f\n',[allperms values].'))
0 0 0 0 0 0 : 0.500000
0 0 0 0 0 1 : 0.750000
0 0 0 0 1 0 : 0.625000
0 0 0 0 1 1 : 0.875000
0 0 0 1 0 0 : 0.562500
0 0 0 1 0 1 : 0.812500
0 0 0 1 1 0 : 0.687500
0 0 0 1 1 1 : 0.937500
0 0 1 0 0 0 : 1.000000
0 0 1 0 0 1 : 1.500000
0 0 1 0 1 0 : 1.250000
0 0 1 0 1 1 : 1.750000
0 0 1 1 0 0 : 1.125000
0 0 1 1 0 1 : 1.625000
0 0 1 1 1 0 : 1.375000
0 0 1 1 1 1 : 1.875000
0 1 0 0 0 0 : 2.000000
0 1 0 0 0 1 : 3.000000
0 1 0 0 1 0 : 2.500000
0 1 0 0 1 1 : 3.500000
0 1 0 1 0 0 : 2.250000
0 1 0 1 0 1 : 3.250000
0 1 0 1 1 0 : 2.750000
0 1 0 1 1 1 : 3.750000
0 1 1 0 0 0 : 4.000000
0 1 1 0 0 1 : 6.000000
0 1 1 0 1 0 : 5.000000
0 1 1 0 1 1 : 7.000000
0 1 1 1 0 0 : 4.500000
0 1 1 1 0 1 : 6.500000
0 1 1 1 1 0 : 5.500000
0 1 1 1 1 1 : 7.500000
1 0 0 0 0 0 : -0.500000
1 0 0 0 0 1 : -0.750000
1 0 0 0 1 0 : -0.625000
1 0 0 0 1 1 : -0.875000
1 0 0 1 0 0 : -0.562500
1 0 0 1 0 1 : -0.812500
1 0 0 1 1 0 : -0.687500
1 0 0 1 1 1 : -0.937500
1 0 1 0 0 0 : -1.000000
1 0 1 0 0 1 : -1.500000
1 0 1 0 1 0 : -1.250000
1 0 1 0 1 1 : -1.750000
1 0 1 1 0 0 : -1.125000
1 0 1 1 0 1 : -1.625000
1 0 1 1 1 0 : -1.375000
1 0 1 1 1 1 : -1.875000
1 1 0 0 0 0 : -2.000000
1 1 0 0 0 1 : -3.000000
1 1 0 0 1 0 : -2.500000
1 1 0 0 1 1 : -3.500000
1 1 0 1 0 0 : -2.250000
1 1 0 1 0 1 : -3.250000
1 1 0 1 1 0 : -2.750000
1 1 0 1 1 1 : -3.750000
1 1 1 0 0 0 : -4.000000
1 1 1 0 0 1 : -6.000000
1 1 1 0 1 0 : -5.000000
1 1 1 0 1 1 : -7.000000
1 1 1 1 0 0 : -4.500000
1 1 1 1 0 1 : -6.500000
1 1 1 1 1 0 : -5.500000
1 1 1 1 1 1 : -7.500000

If you want to write all permutations in a simple way, use dec2bin to get the binary values like @Bart recommended.

However, this kind of operation can often be done significantly more efficient if you use vectorization.

So instead of looping over all values and obtaining the results 1 by one, simply do this:

x = dec2bin(1:2^6-1);

If you want the output to be a matrix, also do this:

x = x - '0';