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

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

Вот какой-то псевдокод. Одни и те же рекурсивные вызовы можно вырезать, сохраняя значения для каждого вызова по ходу и перед проверкой рекурсивного вызова, если значение вызова уже присутствует.

В следующем алгоритме будут все подмножества, кроме пустого.

list * subsets(string s, list * v){
    if(s.length() == 1){
        list.add(s);    
        return v;
    }
    else
    {
        list * temp = subsets(s[1 to length-1], v);     
        int length = temp->size();

        for(int i=0;i<length;i++){
            temp.add(s[0]+temp[i]);
        }

        list.add(s[0]);
        return temp;
    }
}

Answer 2

Вот решение в Scala:

def subsets[T](s : Set[T]) : Set[Set[T]] = 
  if (s.size == 0) Set(Set()) else { 
    val tailSubsets = subsets(s.tail); 
    tailSubsets ++ tailSubsets.map(_ + s.head) 
} 

Answer 3

Элегантное рекурсивное решение, которое соответствует объяснению лучшего ответа выше. Основной вектор операции составляет всего 4 строки. Благодарность книге «Руководство по конкурентному программированию» от Laaksonen, Antti.

// #include <iostream>
#include <vector>
using namespace std;

vector<int> subset;
void search(int k, int n) {
    if (k == n+1) {
    // process subset - put any of your own application logic
    // for (auto i : subset) cout<< i << " ";
    // cout << endl;
    }
    else {
        // include k in the subset
        subset.push_back(k);
        search(k+1, n);
        subset.pop_back();
        // don't include k in the subset
        search(k+1,n);
    }
}

int main() {
    // find all subset between [1,3]
    search(1, 3);
}

Answer 4

Этот вопрос старый. Но есть простое элегантное рекурсивное решение проблемы ОП.

using namespace std;
void recsub(string sofar, string rest){
  if(rest=="") cout<<sofar<<endl;
  else{
    recsub(sofar+rest[0], rest.substr(1)); //including first letter
    recsub(sofar, rest.substr(1)); //recursion without including first letter.
  }
}
void listsub(string str){
  recsub("",str);
}
int main(){
  listsub("abc");
  return 0;
}

//output
abc
ab
ac
a
bc
b
c

//end: there's a blank output too representing empty subset

Answer 5

Для тех, кто хочет простую реализацию с использованием std :: vector и std :: set для алгоритма Майкла Боргвардта:

// Returns the subsets of given set
vector<set<int> > subsets(set<int> s) {
    vector<set<int> > s1, s2;
    set<int> empty;
    s1.push_back(empty); // insert empty set
    // iterate over each element in the given set
    for(set<int>::iterator it=s.begin(); it!=s.end(); ++it) {
        s2.clear(); // clear all sets in s2
        // create subsets with element (*it)
        for(vector<set<int> >::iterator s1iter=s1.begin(); s1iter!=s1.end(); ++s1iter) {
            set<int> temp = *s1iter;
            temp.insert(temp.end(), *it);
            s2.push_back(temp);
        }
        // update s1 with new sets including current *it element
        s1.insert(s1.end(), s2.begin(), s2.end());
    }
    // return
    return s1;
}

Answer 6

простая битовая маскировка может сделать трюк, как обсуждалось ранее .... от rgamber

#include<iostream>
#include<cstdio>

#define pf printf
#define sf scanf

using namespace std;

void solve(){

            int t; char arr[99];
            cin >> t;
            int n = t;
            while( t-- )
            {
                for(int l=0; l<n; l++) cin >> arr[l];
                for(int i=0; i<(1<<n); i++)
                {
                    for(int j=0; j<n; j++)
                        if(i & (1 << j))
                        pf("%c", arr[j]);
                    pf("\n");
                }
            }
        }

int main() {
      solve();
      return 0;
}

Answer 7

вот мое рекурсивное решение.

vector<vector<int> > getSubsets(vector<int> a){


//base case
    //if there is just one item then its subsets are that item and empty item
    //for example all subsets of {1} are {1}, {}

    if(a.size() == 1){
        vector<vector<int> > temp;
        temp.push_back(a);

        vector<int> b;
        temp.push_back(b);

        return temp;

    }
    else
    {


         //here is what i am doing

         // getSubsets({1, 2, 3})
         //without = getSubsets({1, 2})
         //without = {1}, {2}, {}, {1, 2}

         //with = {1, 3}, {2, 3}, {3}, {1, 2, 3}

         //total = {{1}, {2}, {}, {1, 2}, {1, 3}, {2, 3}, {3}, {1, 2, 3}}

         //return total

        int last = a[a.size() - 1];

        a.pop_back();

        vector<vector<int> > without = getSubsets(a);

        vector<vector<int> > with = without;

        for(int i=0;i<without.size();i++){

            with[i].push_back(last);

        }

        vector<vector<int> > total;

        for(int j=0;j<without.size();j++){
            total.push_back(without[j]);
        }

        for(int k=0;k<with.size();k++){
            total.push_back(with[k]);
        }


        return total;
    }


}

Answer 8

одним простым способом будет следующий псевдокод:

Set getSubsets(Set theSet)
{
  SetOfSets resultSet = theSet, tempSet;


  for (int iteration=1; iteration < theSet.length(); iteration++)
    foreach element in resultSet
    {
      foreach other in resultSet
        if (element != other && !isSubset(element, other) && other.length() >= iteration)
          tempSet.append(union(element, other));
    }
    union(tempSet, resultSet)
    tempSet.clear()
  }

}

Ну, я не совсем уверен, что это правильно, но выглядит нормально.