all_subsets

function all_subsets(A)
% Функция выводит все подмножества B множества A, кроме пустого
% Здесь используется написанная нами функция all_k_subsets(k, A);
    for i=0:length(A)
        all_k_subsets(i, A);
    end
end

% На всякий случай , функция all_k_subsets(k, A) была скопирована ниже


function all_k_subsets(k, A)
% Функция выводит все подмножества B множества A длины k

    n = length(A); % мощность множества A
    x = first(n, k); % Первая последовательность нулей и единиц.
% x(i) == 0 , если элемент A(i) не входит в данное подмножество B
% x(i) == 1 , если элемент A(i) входит в данное подмножество B

    B = get_subset(A, k, x); % Первое подмножество из k элементов
    disp(B);

    while ~last(x, n) % Пока не достигнуто последнее подмножество
        x = next(x, n); % Получаем следующую последовательность 0 и 1
        B = get_subset(A, k, x); % Получаем подмножество A
        disp(B);
    end

end

function B = get_subset(A, k, x)
% Функция выбирает отдельные элементы из множества A в зависимости от их
% включения в подмножество B. Включение задается массивом x.
% k - мощность подмножества B

    B = zeros(1, k); % Изначально, B - пустое подмножество
    len_B = 0; % Текущее количество элементов в подмножестве B

    for i=1:length(x)
        if ( x(i) == 1 ) % Если элемент включен
            len_B = len_B + 1; % Увеличиваем текущее количество элементов в подмножестве B
            B(len_B) = A(i); % Записываем очередной элемент в подмножество B
        end
    end
end


function m = first(n, k)
% Функция получает первое подмножество: сначала идут нули, а затем k единиц
    m = ones(1, n);
    for i=1:n-k
        m(i) = 0;
    end
end

function result = last(m, n)
% Функция определяет, является ли текущая последовательность последней

% Ищем такой ноль, справа от которого находится единица.
% Если он найден, то последовательность не последняя.
    result = true;
    for i=1:n-1
        if ( m(i) == 0 ) && ( m(i+1) == 1 )
            result = false;
            break;
        end
    end
end

function m = next(m, n)
% Функция получает следующую последовательность из текущей

% Нам нужно оставить неизменным суммарное количество единиц и нулей в последовательности

% Ищем ближайший с правого конца ноль, справа от которого находится единица
    for t=n-1:(-1):1
        if ( m(t) == 0 ) && ( m(t+1) == 1 )
            break;
        end
    end
% m(t) - элемент, который мы должны изменить с 0 на 1

% Посчитаем число нулей справа от m(t) включая m(t)
    num_zeros = 0;
    for i = t:n
        if ( m(i) == 0 )
            num_zeros = num_zeros + 1;
        end
    end

% Меняем выбранный нами ранее разряд t с нуля на единицу
    m(t) = 1;

% Затем справа от m(t) ставим нужное число нулей:
% Сначала ставим все нули, пока не потратим весь запас
% Затем ставим только единицы

    for i=t+1:n
        if ( num_zeros > 0 ) % Если есть еще запас нулей
            m(i) = 0; % Ставим ноль
            num_zeros = num_zeros - 1; % Уменьшаем запас нулей
        else % Иначе ставим единицу
            m(i) = 1;
        end
    end
end