Нахождение всех подмножеств множества

Question

Мне нужен алгоритм, чтобы найти все подмножества набора, в котором количество элементов в наборе равно n.

S={1,2,3,4...n}

Редактировать: У меня проблемы с пониманием ответов, предоставленных до сих пор. Я хотел бы иметь пошаговые примеры того, как ответы работают, чтобы найти подмножества.

Например,

S={1,2,3,4,5}

Откуда вы знаете, {1} и {1,2} являются подмножествами?

Может ли кто-нибудь помочь мне с простой функцией в c ++ найти подмножества {1,2,3,4,5}

Answer 1

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

• Для n = 1 набор подмножеств равен {{}, {1}}
• Для n> 1 найдите набор подмножеств 1, ..., n-1 и сделайте две его копии. Для одного из них добавьте n к каждому подмножеству. Затем возьмите объединение двух копий.

Редактировать Чтобы сделать его кристально чистым:

• Множество подмножеств {1}: {{}, {1}}
• Для {1, 2}, возьмите {{}, {1}}, добавьте 2 к каждому подмножеству, чтобы получить {{2}, {1, 2}} и возьмите объединение с {{}, {1} } чтобы получить {{}, {1}, {2}, {1, 2}}
• Повторяйте, пока не достигнете n

Answer 2

Слишком поздно, чтобы ответить, но итеративный подход здесь звучит легко:

1) для набора n элементов получите значение 2^n. Там будет 2 ^ n подмножеств. (2 ^ n, потому что каждый элемент может присутствовать (1) или отсутствовать (0). Таким образом, для n элементов будет 2 ^ n подмножеств.). Например:
for 3 elements, say {a,b,c}, there will be 2^3=8 subsets

2) Получить двоичное представление 2^n. Например:
8 in binary is 1000

3) Переход от 0 к (2^n - 1). На каждой итерации для каждого 1 в двоичном представлении формируют подмножество с элементами, которые соответствуют индексу этого 1 в двоичном представлении. Например:

For the elements {a, b, c}
000 will give    {}
001 will give    {c}
010 will give    {b}
011 will give    {b, c}
100 will give    {a}
101 will give    {a, c}
110 will give    {a, b}
111 will give    {a, b, c}

4) Выполните объединение всех подмножеств, найденных на шаге 3. Вернитесь Например:
Simple union of above sets!

Answer 3

На случай, если кто-нибудь придет и все еще будет удивляться, вот функция, использующая объяснение Майкла в C ++

vector< vector<int> > getAllSubsets(vector<int> set)
{
    vector< vector<int> > subset;
    vector<int> empty;
    subset.push_back( empty );

    for (int i = 0; i < set.size(); i++)
    {
        vector< vector<int> > subsetTemp = subset;

        for (int j = 0; j < subsetTemp.size(); j++)
            subsetTemp[j].push_back( set[i] );

        for (int j = 0; j < subsetTemp.size(); j++)
            subset.push_back( subsetTemp[j] );
    }
    return subset;
}

Примите во внимание, что это вернет набор размером 2 ^ N со ВСЕМИ возможными подмножествами, то есть, возможно, будут дубликаты. Если вы не хотите этого, я бы предложил использовать set вместо vector (который я использовал, чтобы избежать итераторов в коде).

Answer 4

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

Answer 5

Здесь я объяснил это подробно. Делайте upvote, если вам нравится пост в блоге.

http://cod3rutopia.blogspot.in/

В любом случае, если вы не можете найти мой блог, вот объяснение.

Это проблема рекурсивного характера.

По существу, для элемента, присутствующего в подмножестве, есть 2 варианта:

1) присутствует в наборе

2) Отсутствует в наборе.

По этой причине набор из n чисел имеет 2 ^ n подмножеств (2 варианта на элемент)

Вот псевдокод (C ++) для печати всех подмножеств, за которым следует пример, объясняющий, как работает код. 1) [] - это массив чисел, подмножества которых вы хотите узнать. 2) bool a [] - массив логических значений, где a [i] сообщает, присутствует ли число A [i] в ​​наборе или нет.

print(int A[],int low,int high)  
   {
    if(low>high)  
    {
     for(all entries i in bool a[] which are true)  
        print(A[i])
    }  
   else  
   {set a[low] to true //include the element in the subset  
    print(A,low+1,high)  
    set a[low] to false//not including the element in the subset  
    print(A,low+1,high)
   }  
  }  

Answer 6

Вот простой рекурсивный алгоритм в Python для поиска всех подмножеств набора:

def find_subsets(so_far, rest):
        print 'parameters', so_far, rest
        if not rest:
            print so_far
        else:
            find_subsets(so_far + [rest[0]], rest[1:])
            find_subsets(so_far, rest[1:])


find_subsets([], [1,2,3])

Вывод будет следующим: $ python subsets.py

parameters [] [1, 2, 3]
parameters [1] [2, 3]
parameters [1, 2] [3]
parameters [1, 2, 3] []
[1, 2, 3]
parameters [1, 2] []
[1, 2]
parameters [1] [3]
parameters [1, 3] []
[1, 3]
parameters [1] []
[1]
parameters [] [2, 3]
parameters [2] [3]
parameters [2, 3] []
[2, 3]
parameters [2] []
[2]
parameters [] [3]
parameters [3] []
[3]
parameters [] []
[]

Посмотрите следующее видео из Стэнфорда для хорошего объяснения этого алгоритма:

https://www.youtube.com/watch?v=NdF1QDTRkck&feature=PlayList&p=FE6E58F856038C69&index=9

Answer 7

Вот реализация решения Майкла для любого типа элемента в std :: vector.

#include <iostream>
#include <vector>

using std::vector;
using std::cout;
using std::endl;

// Find all subsets
template<typename element>
vector< vector<element> > subsets(const vector<element>& set)
{
  // Output
  vector< vector<element> > ss;
  // If empty set, return set containing empty set
  if (set.empty()) {
    ss.push_back(set);
    return ss;
  }

  // If only one element, return itself and empty set
  if (set.size() == 1) {
    vector<element> empty;
    ss.push_back(empty);
    ss.push_back(set);
    return ss;
  }

  // Otherwise, get all but last element
  vector<element> allbutlast;
  for (unsigned int i=0;i<(set.size()-1);i++) {
    allbutlast.push_back( set[i] );
  }
  // Get subsets of set formed by excluding the last element of the input set
  vector< vector<element> > ssallbutlast = subsets(allbutlast);
  // First add these sets to the output
  for (unsigned int i=0;i<ssallbutlast.size();i++) {
    ss.push_back(ssallbutlast[i]);
  }
  // Now add to each set in ssallbutlast the last element of the input
  for (unsigned int i=0;i<ssallbutlast.size();i++) {
    ssallbutlast[i].push_back( set[set.size()-1] );
  }
  // Add these new sets to the output
  for (unsigned int i=0;i<ssallbutlast.size();i++) {
    ss.push_back(ssallbutlast[i]);
  }

  return ss;

}

// Test
int main()
{

  vector<char> a;
  a.push_back('a');
  a.push_back('b');
  a.push_back('c');


  vector< vector<char> > sa = subsets(a);

  for (unsigned int i=0;i<sa.size();i++) {
    for (unsigned int j=0;j<sa[i].size();j++) {
      cout << sa[i][j];
    }
    cout << endl;
  }

  return 0;

}

Выход:

(empty line)
a
b
ab
c
ac
bc
abc

Answer 8

Вам не нужно связываться с рекурсией и другими сложными алгоритмами. Вы можете найти все подмножества, используя битовые комбинации (от десятичных до двоичных) всех чисел от 0 до 2 ^ (N-1). Здесь N - количество элементов или количество элементов в этом наборе. Техника объясняется здесь с реализацией и демонстрацией.

http://codeding.com/?article=12

Answer 9

Вниз с O (n) пробелом

#include <stdio.h>

void print_all_subset(int *A, int len, int *B, int len2, int index)
{
    if (index >= len)
    {
        for (int i = 0; i < len2; ++i)
        {
            printf("%d ", B[i]);
        }
        printf("\n");

        return;
    }
    print_all_subset(A, len, B, len2, index+1);

    B[len2] = A[index];
    print_all_subset(A, len, B, len2+1, index+1);
}



int main()
{
    int A[] = {1, 2, 3, 4, 5, 6, 7};
    int B[7] = {0};

    print_all_subset(A, 7, B, 0, 0);
}

Answer 10

Вот рабочий код, который я написал некоторое время назад

// Return all subsets of a given set
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<sstream>
#include<cstring>
#include<climits>
#include<cmath>
#include<iterator>
#include<set>
#include<map>
#include<stack>
#include<queue>
using namespace std;


typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector< vector<int> > vvi;
typedef vector<string> vs;

vvi get_subsets(vi v, int size)
{
    if(size==0) return vvi(1);
    vvi subsets = get_subsets(v,size-1);

    vvi more_subsets(subsets);

    for(typeof(more_subsets.begin()) it = more_subsets.begin(); it !=more_subsets.end(); it++)
    {
        (*it).push_back(v[size-1]);
    }

    subsets.insert(subsets.end(), (more_subsets).begin(), (more_subsets).end());
    return subsets;
}

int main()
{
    int ar[] = {1,2,3};
    vi v(ar , ar+int(sizeof(ar)/sizeof(ar[0])));
    vvi subsets = get_subsets(v,int((v).size()));


    for(typeof(subsets.begin()) it = subsets.begin(); it !=subsets.end(); it++)
    {
        printf("{ ");

        for(typeof((*it).begin()) it2 = (*it).begin(); it2 !=(*it).end(); it2++)
        {
            printf("%d,",*it2 );
        }
        printf(" }\n");
    }
    printf("Total subsets = %d\n",int((subsets).size()) );
}