Вычисление всех подмножеств набора чисел - PullRequest
Новая
       3

Вычисление всех подмножеств набора чисел

38 голосов
/ 09 января 2011

Я хочу найти подмножества набора целых чисел.Это первый шаг алгоритма «Сумма подмножеств» с возвратом.Я написал следующий код, но он не возвращает правильный ответ: 

BTSum(0, nums);
///**************
ArrayList<Integer> list = new ArrayList<Integer>();

public static ArrayList<Integer> BTSum(int n, ArrayList<Integer> numbers) {
    if (n == numbers.size()) {
        for (Integer integer : list) {
            System.out.print(integer+", ");
        }
        System.out.println("********************");
        list.removeAll(list);
        System.out.println();
    } else {
        for (int i = n; i < numbers.size(); i++) {
            if (i == numbers.size() - 1) {
                list.add(numbers.get(i));
                BTSum(i + 1, numbers);
            } else {
                list.add(numbers.get(i));
                for (int j = i+1; j < numbers.size(); j++)
                BTSum(j, numbers);
            }
        }
    }

    return null;
}

Например, если я хочу вычислить подмножества set = {1, 3, 5} Результат моегометод: 

 1, 3, 5, ********************

 5, ********************

 3, 5, ********************

 5, ********************

 3, 5, ********************

 5, ********************

Я хочу, чтобы он выдал: 

1, 3, 5 
1, 5
3, 5
5

Я думаю, что проблема в части list.removeAll (list);но я не знаю, как это исправить.

Ответы [ 13 ]

85 голосов
/ 09 января 2011

То, что вы хотите, называется Powerset . Вот простая реализация этого: 

public static Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
        Set<Set<Integer>> sets = new HashSet<Set<Integer>>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<Integer>());
            return sets;
        }
        List<Integer> list = new ArrayList<Integer>(originalSet);
        Integer head = list.get(0);
        Set<Integer> rest = new HashSet<Integer>(list.subList(1, list.size()));
        for (Set<Integer> set : powerSet(rest)) {
            Set<Integer> newSet = new HashSet<Integer>();
            newSet.add(head);
            newSet.addAll(set);
            sets.add(newSet);
            sets.add(set);
        }
        return sets;
    }

Я дам вам пример, чтобы объяснить, как алгоритм работает для powerset {1, 2, 3}:

  • Удалить {1} и выполнить powerset для {2, 3};
    • Удалить {2} и выполнить powerset для {3};
      • Удалить {3} и выполнить powerset для {};
        • Powerset {} равен {{}};
      • Блок питания {3} равен 3 в сочетании с {{}} = { {}, {3} };
    • Блок питания {2, 3} равен {2} в сочетании с { {}, {3} } = { {}, {3}, {2}, {2, 3} };
  • Блок питания {1, 2, 3} равен {1} в сочетании с { {}, {3}, {2}, {2, 3} } = { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} }.
22 голосов
/ 09 января 2011

Просто учебник для начинающих, как вы могли бы решить проблему:

Подход 1

  • Возьмите первый элемент вашего списка номеров
  • создать все подмножества из списка оставшихся номеров (то есть списка номеров без выбранного) => Рекурсия!
  • для каждого подмножества, найденного на предыдущем шаге, добавить само подмножество и подмножествосоединяется с элементом, выбранным на шаге 1, для вывода.

Конечно, вы должны проверить базовый случай, т.е. если ваш список номеров пуст.

Подход 2

Хорошо известен факт, что набор с n элементами имеет 2^n подмножеств.Таким образом, вы можете считать в двоичном виде от 0 до 2^n и интерпретировать двоичное число как соответствующее подмножество.Обратите внимание, что для этого подхода требуется двоичное число с достаточным количеством цифр для представления всего набора.

Преобразование одного из двух подходов в код должно быть не слишком большой проблемой.

15 голосов
/ 09 января 2011

Ваш код действительно сбивает с толку, и нет никаких объяснений.

Вы можете делать итеративно с битовой маской, которая определяет, какие числа в наборе.Каждое число от 0 до 2 ^ n дает уникальное подмножество в своем двоичном представлении, например

для n = 3:

i = 5 -> 101 в двоичном формате, выберите первый и последний элементыi = 7 -> 111 в двоичном коде, выберите первые 3 элемента

Предположим, что существует n элементов (n <64, в конце концов, если n больше 64, вы запустите это навсегда). </p> 

for(long i = 0; i < (1<<n); i++){
    ArrayList<Integer> subset = new ArrayList<Integer>();
    for(int j = 0; j < n; j++){
        if((i>>j) & 1) == 1){ // bit j is on
            subset.add(numbers.get(j));
        }
    }
    // print subset
}
8 голосов
/ 11 июля 2014

Учитывая посетителя Noob (спасибо Google) на этот вопрос - like me
Вот рекурсивное решение, которое работает на простом принципе:

Set = {a, b, c, d, e}
тогда мы можем разбить его на {a} + Subset of {b,c,d,e}

public class Powerset{
     String str = "abcd"; //our string
     public static void main(String []args){
        Powerset ps = new Powerset();
        for(int i = 0; i< ps.str.length();i++){ //traverse through all characters
            ps.subs("",i);
        }
     }

     void subs(String substr,int index)
     {
         String s = ""+str.charAt(index); //very important, create a variable on each stack
         s = substr+s; //append the subset so far
         System.out.println(s); //print

         for(int i=index+1;i<str.length();i++)
           subs(s,i); //call recursively

     }
}

OUTPUT 

a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd
d
5 голосов
/ 15 июня 2016

Понятно, что общее количество подмножеств любого данного набора равно 2 ^ (количество элементов в наборе).Если установлено

A = {1, 2, 3}

, то подмножество A будет:

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

Если мы посмотрим, это похоже на двоичный файлномера.

{000}, {001}, {010}, {011}, {100}, {101}, {110}, {111}

Если принять во внимание выше: 

static void subSet(char[] set) {
        int c = set.length;

        for (int i = 0; i < (1 << c); i++) {
            System.out.print("{");
            for (int j = 0; j < c; j++) {
                if ((i & (1 << j)) > 0) {
                    System.out.print(set[j] + " ");
                }
            }
            System.out.println("}");
        }
    }

    public static void main(String[] args) {
        char c[] = {'a', 'b', 'c'};
        subSet(c);
    }
2 голосов
/ 20 января 2014

Основываясь на том, что я узнал сегодня, вот Java-решение. Оно основано на recursion

public class Powerset {

    public static void main(String[] args) {
        final List<List<String>> allSubsets = powerSet(Arrays.asList(1, 2, 3, 4), 0);
        for (List<String> subsets : allSubsets) {
            System.out.println(subsets);
        }
    }

    private static List<List<String>> powerSet(final List<Integer> values,
                                               int index) {
        if (index == values.size()) {
            return new ArrayList<>();
        }
        int val = values.get(index);
        List<List<String>> subset = powerSet(values, index + 1);
        List<List<String>> returnList = new ArrayList<>();
        returnList.add(Arrays.asList(String.valueOf(val)));
        returnList.addAll(subset);
        for (final List<String> subsetValues : subset) {
            for (final String subsetValue : subsetValues) {
                returnList.add(Arrays.asList(val + "," + subsetValue));
            }
        }
        return returnList;
    }
}

Запуск его даст результаты как 

[1]
[2]
[3]
[4]
[3,4]
[2,3]
[2,4]
[2,3,4]
[1,2]
[1,3]
[1,4]
[1,3,4]
[1,2,3]
[1,2,4]
[1,2,3,4]
2 голосов
/ 18 декабря 2012 
private static void findSubsets(int array[])
{
  int numOfSubsets = 1 << array.length; 

  for(int i = 0; i < numOfSubsets; i++)
 {
    int pos = array.length - 1;
   int bitmask = i;

   System.out.print("{");
   while(bitmask > 0)
   {
    if((bitmask & 1) == 1)
     System.out.print(array[pos]+",");
    bitmask >>= 1;
    pos--;
   }
   System.out.print("}");
 }
}
1 голос
/ 30 августа 2018

Если вы имеете дело с большой коллекцией элементов, вы можете (хотя и маловероятно) столкнуться с проблемами переполнения стека. Я допускаю, что у вас больше шансов исчерпать память до того, как вы переполните стек, но я все равно добавлю этот нерекурсивный метод. 

public static final <T> Set<Set<T>> powerSet(final Iterable<T> original) {
  Set<Set<T>> sets = new HashSet<>();
  sets.add(new HashSet<>());

  for (final T value : original) {
    final Set<Set<T>> newSets = new HashSet<>(sets);

    for (final Set<T> set : sets) {
      final Set<T> newSet = new HashSet<>(set);
      newSet.add(value);
      newSets.add(newSet);
    }

    sets = newSets;
  }

  return sets;
}

Или, если вы предпочитаете работать с массивами: 

@SuppressWarnings("unchecked")
public static final <T> T[][] powerSet(final T... original) {
  T[][] sets = (T[][]) Array.newInstance(original.getClass(), 1);
  sets[0] = Arrays.copyOf(original, 0);

  for (final T value : original) {
    final int oldLength = sets.length;
    sets = Arrays.copyOf(sets, oldLength * 2);

    for (int i = 0; i < oldLength; i++) {
      final T[] oldArray = sets[i];
      final T[] newArray = Arrays.copyOf(oldArray, oldArray.length + 1);
      newArray[oldArray.length] = value;
      sets[i + oldLength] = newArray;
    }
  }

  return sets;
}
1 голос
/ 27 января 2016 
public static ArrayList<ArrayList<Integer>> powerSet(List<Integer> intList) {

    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    result.add(new ArrayList<Integer>());

    for (int i : intList) {
        ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();

        for (ArrayList<Integer> innerList : result) {
            innerList = new ArrayList<Integer>(innerList);
            innerList.add(i);
            temp.add(innerList);
        }
        result.addAll(temp);
    }

    return result;
}
1 голос
/ 19 марта 2012 
// subsets for the set of 5,9,8

import java.util.ArrayList;
import java.util.List;

public class Subset {
    public static void main(String[] args) {
    List<Integer> s = new ArrayList<Integer>();
    s.add(9);
    s.add(5);
    s.add(8);
    int setSize = s.size();
    int finalValue = (int) (Math.pow(2, setSize));
    String bValue = "";
    for (int i = 0; i < finalValue; i++) {
        bValue = Integer.toBinaryString(i);
        int bValueSize = bValue.length();
        for (int k = 0; k < (setSize - bValueSize); k++) {
            bValue = "0" + bValue;
        }
        System.out.print("{ ");
        for (int j = 0; j < setSize; j++) {
            if (bValue.charAt(j) == '1') {
                System.out.print((s.get(j)) + " ");
            }
        }
        System.out.print("} ");
    }
}
}


//Output : { } { 8 } { 5 } { 5 8 } { 9 } { 9 8 } { 9 5 } { 9 5 8 }
Страница:
...