Почему мой код не работает для вывода всех подмножеств набора работ? - PullRequest
Новая
       65

Почему мой код не работает для вывода всех подмножеств набора работ?

0 голосов
/ 24 февраля 2020

Я пытаюсь написать код для вывода всех подмножеств набора (представленных списком целых чисел). Почему следующий код не работает? 

public static List<List<Integer>> powerSet(List<Integer> l){
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if (l.size() == 0) {
        result.add(new ArrayList<>());
    }
    else { 
        List<List<Integer>> prev = powerSet(l.subList(0, l.size() - 1));
        for (List<Integer> x : prev) {
            x.add(l.get(l.size() - 1));
            result.add(x);
        }
    }
    return result;
}

Я думаю, что для вычисления подмножеств множества A [0 ... n-1] размера n мы можем просто добавить последний элемент A [n - 1] множества для подмножеств A [0 ... n-2]. Тем не менее, код выше дает мне только тот же набор: 

public static void main(String[] args) {

    List<Integer> l = new ArrayList<>();
    l.add(0);
    l.add(1);
    l.add(2);

    List<List<Integer>> result = powerSet(l);

    System.out.println(result.toString());
}

1 Ответ

1 голос
/ 24 февраля 2020

Вы могли бы преобразовать его в двоичный файл? Например, если у вас есть 3 элемента, то все возможные ответы будут содержаться в: 

000
001
010
011
100
101
110
111

Итак, 1 = элемент присутствует, 0 = элемент отсутствует

Таким образом, вы просто запускаете al oop в 0 и <2 ^ n </p>

i-й элемент определяется путем взятия 2 и возведения его в степень i.

(Примечание: 2 ^ 0 = 1, 2 ^ 1 = 2, 2 ^ 2 = 4 et c.)

...