Алгоритм нахождения powerset {1,2,3} - PullRequest
Новая
       26

Алгоритм нахождения powerset {1,2,3}

1 голос
/ 30 августа 2011

Я думаю, что это немного сбивает с толку, потому что я никогда не использовал наборы Java. Может кто-нибудь попытаться показать мне (предпочтительно, объясняя, как постепенно создается powerset) в следующем коде (ps я получил этот код из поста на stackoverflow, так что заслуга этого человека): 

public static void main(String[] args) {
        Set<Integer> mySet = new HashSet<Integer>();
        mySet.add(1);
        mySet.add(2);
        mySet.add(3);
        for (Set<Integer> s : powerSet(mySet)) {
            System.out.println(s);
        }

    }

    public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
        Set<Set<T>> sets = new HashSet<Set<T>>();

        //If the input is empty, add the empty set and return
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<T>());
            return sets;
        }

        //Put the originalSet into an arraylist
        List<T> list = new ArrayList<T>(originalSet);

        //Get the first element
        T head = list.get(0);

        //Get everything but the first element and put into a set
        Set<T> rest = new HashSet<T>(list.subList(1, list.size()));

        //For each element in the set above
        for (Set<T> set : powerSet(rest)) {

            //Create a new set
            Set<T> newSet = new HashSet<T>();

            //Add the head
            newSet.add(head);

            //Add the rest
            newSet.addAll(set);

            //Add all of newset to the result
            sets.add(newSet);

            //Add the current element
            sets.add(set);
        }
        return sets;
    }

1 Ответ

1 голос
/ 31 августа 2011

Подумайте о наборе мощности {1, 2, 3}.Мы можем думать об этом как о комбинации: 

{}  
{1} + powerset {2, 3}  
{2} + powerset {3}  
{3} + powerset {}

Если взять строку {1} + powerset {2, 3}, то это расширится до: 

{1} + { {}, {2}, {3}, {2, 3} }

, что в свою очередь станет:

Код делает то же самое, используя рекурсию для генерации меньших наборов мощности и накапливая каждый набор в списке.

...