Task108 (2 способа)

UniLecsTask108.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class UniLecsTask108 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        System.out.println("Всего подмножеств: " + numberOfSubsets(n));
        System.out.println("Набор подмножеств, полученный способом 1:");
        for(Set<Integer> l: getAllSubsetsWithoutRecursion(n))
            System.out.println(l);
        System.out.println("Набор подмножеств, полученный способом 2:");
        for(Set<Integer> l: getAllSubsetsWithRecursion(n))
            System.out.println(l);
    }

    /*
    Способ 1, без рекурсии:
    Каждому подмножеству Mi множества чисел от 1 до N включительно можно поставить в соответствие
    натуральное число i, "номер" этого подмножества, составленный по такому правилу:
    если Mi содержит число n, 1 <= n <= N, то в двоичной записи числа i на позиции n должна стоять 1, иначе 0.
    При заданном N номера подмножеств принимают значения от 0 (0b000...00) до 2^N - 1 (0b111...11),
    т. е. всего возможных подмножеств для заданного N будет 2^N.
    Чтобы получить набор всех подмножеств для заданного N, следует рассмотреть все возможные номера,
    т. е. числа от 0 до 2^N - 1,
    и для каждого из них восстановить подмножество по двоичному представлению.
    */

    public static BigInteger numberOfSubsets(int n) {
        return new BigInteger("2").pow(n);
    }

    public static Set<Integer> getSetByNumber(int n) {
        Set<Integer> result = new TreeSet<>();
        int count = 1;
        while(n != 0) {
            if(n%2 == 1) {
                result.add(count);
                n--;
            }
            n /= 2;
            count++;
        }
        return result;
    }

    public static Set<Set<Integer>> getAllSubsetsWithoutRecursion(int n) {
        Set<Set<Integer>> result = new HashSet<>();
        BigInteger number = numberOfSubsets(n);
        for(int i = 0; BigInteger.valueOf(i).compareTo(number) < 0; i++)
            result.add(getSetByNumber(i));
        return result;
    }

    /*
    Способ 2, через рекурсию:
    Если у нас есть набор всех подмножеств для некоторого N-1, то можно построить
    из него набор для N: каждому подмножеству M из старого набора будет сооветствовать два подмножества в новом наборе -
    само M и M+{N}. Решение для N=0 будет состоять из одного только пустого множества.
    Отсюда также можно получить формулу для количества подмножеств P(N):
    P(0) = 1, P(N) = 2*P(N-1) => P(N) = 2^N
    */

    public static Set<Set<Integer>> getAllSubsetsWithRecursion(int n) {
        Set<Set<Integer>> result = new HashSet<>();
        result.add(new TreeSet<>());
        while(n > 0)
            complementForN(result,n--);
        return result;
    }

    public static void complementForN(Set<Set<Integer>> sourceSets, int n) {
        Set<Set<Integer>> newSets = new HashSet<>();
        for(Set<Integer> s: sourceSets) {
            Set<Integer> newSet = new TreeSet<>(s);
            s.add(n);
            newSets.add(newSet);
        }
        sourceSets.addAll(newSets);
    }

    /*
    Метод для тестирования: результаты, полученные двумя способами, должны совпадать.
    */

    public static void testForN(int n) {
        Set<Set<Integer>> s1 = getAllSubsetsWithoutRecursion(n);
        Set<Set<Integer>> s2 = getAllSubsetsWithRecursion(n);
        if(!s1.equals(s2))
            throw new RuntimeException("Наборы множеств, полученных двумя способами, отличаются!");
        System.out.println("Для N = " + n + " полученные наборы подмножеств идентичны.");
    }

}