Как найти все возможные подмножества заданного массива?

Ответ 1

Учитывая набор S элементов N и заданное подмножество, каждый элемент либо делает, либо не принадлежит этому подмножеству. Следовательно, 2^N возможные подмножества (если вы включаете исходные и пустые множества), и есть прямое сопоставление от битов двоичного представления x между 0 и 2^N к элементам в x th под S.

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

Для нахождения подмножеств, которые равны сумме t для больших N, одна оптимизация может заключаться в записи тех подмножеств, которые превышают t, а не тестируют какие-либо правильные надмножества. Тестирование того, является ли установленное число x надмножеством набора y, может быть достигнуто с помощью одной побитовой операции и целочисленного сравнения.

Ответ 2

То, что вы ищете, называется power set. Rosetta Code имеет множество различных реализаций, но здесь их код на С++ (они используют вектор вместо массива, но это должно быть довольно легко переводить).

#include <iostream>
#include <set>
#include <vector>
#include <iterator>

typedef std::set<int> set_type;
typedef std::set<set_type> powerset_type;

powerset_type powerset(set_type const& set)
{
  typedef set_type::const_iterator set_iter;
  typedef std::vector<set_iter> vec;
  typedef vec::iterator vec_iter;

  struct local
  {
    static int dereference(set_iter v) { return *v; }
  };

  powerset_type result;

  vec elements;
  do
  {
    set_type tmp;
    std::transform(elements.begin(), elements.end(),
                   std::inserter(tmp, tmp.end()),
                   local::dereference);
    result.insert(tmp);
    if (!elements.empty() && ++elements.back() == set.end())
    {
      elements.pop_back();
    }
    else
    {
      set_iter iter;
      if (elements.empty())
      {
        iter = set.begin();
      }
      else
      {
        iter = elements.back();
        ++iter;
      }
      for (; iter != set.end(); ++iter)
      {
        elements.push_back(iter);
      }
    }
  } while (!elements.empty());

  return result;
}

int main()
{
  int values[4] = { 2, 3, 5, 7 };
  set_type test_set(values, values+4);

  powerset_type test_powerset = powerset(test_set);

  for (powerset_type::iterator iter = test_powerset.begin();
       iter != test_powerset.end();
       ++iter)
  {
    std::cout << "{ ";
    char const* prefix = "";
    for (set_type::iterator iter2 = iter->begin();
         iter2 != iter->end();
         ++iter2)
    {
      std::cout << prefix << *iter2;
      prefix = ", ";
    }
    std::cout << " }\n";
  }
}

Вывод:

{  }
{ 2 }
{ 2, 3 }
{ 2, 3, 5 }
{ 2, 3, 5, 7 }
{ 2, 3, 7 }
{ 2, 5 }
{ 2, 5, 7 }
{ 2, 7 }
{ 3 }
{ 3, 5 }
{ 3, 5, 7 }
{ 3, 7 }
{ 5 }
{ 5, 7 }
{ 7 }

Ответ 3

Это был один из моих проектов в колледже 4/5 лет назад, и я не могу хорошо напомнить алгоритм. Как я вижу, и моя память обслуживает его, используя массив как исходный набор и битовую маску, чтобы указать, какие элементы присутствуют в текущем подмножестве.
здесь не проверенный код из архива:

#include <iostream>

#ifndef H_SUBSET
#define H_SUBSET

template <class T>
class Subset {
    private:
        int Dimension;
        T *Set;
        bool *Bitmask;
    public:
        Subset(T *set, int dim);
        ~Subset(void);
        void Show(void);
        void NextSubset(void);
        void EmptySet(void);
        void FullSet(void);
        int SubsetCardinality(void);
        int SetCardinality(void);
        T operator[](int index);
};      

template <class T>
int Subset<T>::SetCardinality(void) {
    return Dimension;
}

template <class T>
int Subset<T>::SubsetCardinality(void) {
    int dim = 0;
    for(int i = 0; i<Dimension; i++) {
        if(Bitmask[i]) {
            dim++;
        }
    }
    return dim;
}

template <class T>
void Subset<T>::EmptySet(void) {
    for(int i = 0; i<Dimension; i++) {
        Bitmask[i] = 0;
    }
    return;
}

template <class T>
void Subset<T>::FullSet(void) {
    for(int i = 0; i<Dimension; i++) {
        Bitmask[i] = 1;
    }
    return;
}

template <class T>
void Subset<T>::NextSubset(void) {
    int i = Dimension - 1;
    while(!Bitmask[i]&&i>=0) {
        i--;
        if(i<0) {
            break;
        }
    }
    if(i>=0) {
        Bitmask[i] = !Bitmask[i];
    }
    for(int j = i+1; j < Dimension; j++) {
        Bitmask[j] = !Bitmask[j];
    }
    return;
}

template <class T>
void Subset<T>::Show(void) {
    std::cout << "{ ";
    for(int i=0; i<Dimension; i++) {
        if(Bitmask[i]) {
            std::cout << Set[i] << ", ";
        }
    }
    std::cout << "}";
    return;
}

template <class T>
Subset<T>::Subset(T *set, int dim) {
    Set = new T[dim];
    Bitmask = new bool[dim];
    Dimension = dim;
    for(int i=0; i<dim; i++) {
        Set[i] = set[i];
        Bitmask[i] = true;
    }
}

template <class T>
Subset<T>::~Subset(void) {
    delete [] Set;
    delete [] Bitmask;
}
#endif // H_SUBSET

И если это твоя домашняя работа, ты убиваешь себя братом;)

Ответ 4

Вы:

A) Действительно хотите найти все возможные подмножества?

или

B) Хотите узнать, сколько элементов в массиве можно объединить, чтобы равное заданному числу, и увидеть A) как шаг к решению?

Если это A), то это довольно просто, но число возможных подмножеств очень быстро смешно.

Если это B), тогда вы должны сначала отсортировать массив и работать оттуда.