Перестановки 0 и 1 с рекурсией

Question

Я пытаюсь записать все 6-битные перестановки 0 и 1 с использованием рекурсии (то есть [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]). Я следую совету, полученному от Yahoo! Ответы У меня есть следующее, но оно не доходит до конца, и есть повторяющиеся записи.

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) < 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

Выход (MATLAB) просто:

>> 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

Answer 1

Если вы хотите вычислить каждое возможное значение 6-битного числа, есть гораздо более эффективные способы сделать это, чем с помощью рекурсии.Использование функции DEC2BIN является одним из вариантов, но этот предыдущий вопрос показывает, что реализации, использующие функцию BITGET или индексацию через справочную таблицу, выполняются намного быстрее.Например, вот одно из возможных решений:

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

Затем вы можете применить вашу converter функцию к результату построчно:

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);

И вы можете отобразитьрезультаты следующие:

>> 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

Answer 2

Просто выполните итерацию от 0 до 2 ⁶ -1 и вызовите функцию Matlab dec2bin(...).Вы можете дополнить результат нулями, используя sprintf(...).

Answer 3

Если вы хотите написать все перестановки простым способом, используйте dec2bin, чтобы получить двоичные значения, такие как рекомендуемый @Bart.

Тем не менее, этот тип операции часто может быть значительно более эффективным, если вы используете векторизацию.

Таким образом, вместо того, чтобы перебирать все значения и получать результаты 1 за одним, просто сделайте это:

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

Если вы хотите, чтобы вывод был матрицей, также сделайте это:

x = x - '0';