2

Изучаю книгу А. Лааксонена "Олимпиадное программирование". Там есть задача о порождении подмножеств, и приведен следующий алгоритм:

Функция манипулирует вектором vector<int> subset, который содержит элементы подмножества. Для начала поиска, вызываем функцию с параметром 1.

void search(int k){
if (k == n + 1){
    //обработать подмножество
} else{
    //включить k в подмножество
    subset.push_back(k);
    search(k+1);
    subset.pop_back();
    search(k+1);
    //не включить k в подмножество
}}

Я не понимаю, как он работает. Нет обращения к элементам множества, для примера {1, 2, 3} подходит, но если это {1, 2, 3, 1}? То уже работать не будет. Вопрос как его доработать, чтобы он правильно находил все подмножества?

1
  • 1
    Если речь идёт о математических множества, то дубликатов там не бывает
    – Eikthyrnir
    19 ноя 2019 в 14:48

4 ответа 4

3

Более плохого решения этой задачи я и представить не могу, оно медленное и представляет интерес только для изучения рекурсии.

Перечисление всех подмножеств в олимпиадном программировании чаще всего выполняется методом представления целочисленной переменной в двоичном виде (если нет особых причин поступать иначе). Допустим, ваше множество - это массив чисел:

const size_t N = 4;
int A[N] = {1, 2, 3, 1};

Далее вам нужна некая переменная, которая будет бежать от 0 до 2**N-1. Допустим, вот так:

for (size_t k=0; k<(1llu<<N); ++k) {
  ...
}

Теперь набор битов в переменной k на каждой итерации этого цикла будет обозначать некое подмножество. Допустим, на каком-то шаге k=5. Это означает, что в двоичном виде (если у нас N = 4 бита только нужны) оно имеет вид 0101. Таким образом, вам нужно взять лишь элементы A с номерами 0 и 2: {1, 3}. Сделать это можно так (это нужно вписать вместо ... в предыдущем цикле):

size_t n = 0;
for (size_t i=0, j=1; i<N; ++i, j<<=1) {
  if (k&j)  B[n++] = A[i];  
}
// Тут обрабатываем массив `B` из `n` элементов - это и есть наше очередное подмножество.

Вот и всё, таким образом, сам по себе перебор подмножество уже за вас делает компьютер, когда вы прибавляете 1 к числу k. Вам нужно только брать единичные биты из k и радоваться. После выполнения цикла по i вы имеете массив B, а число n - это число элементов в нём.

Не забывайте, что здесь имеет место два крайних случая: пустое множество и когда B=A. Их можно убрать, поменяв границы выполнения цикла по k вот так:

for (size_t k=1; k<(1llu<<N)-1; ++k) {
  ...
}

Но тогда уже нельзя делать N меньше 2, потому что получится не то, что вы хотели.

7
  • Не совсем понятно какое отношение этот ответ имеет к заданному вопросу. Во-первых, тут очень не приветствуются ответы в стиле "выкинь нафиг свое и делай как я". Во-вторых, вопрос задан по содержанию книги. Эффективность исходного варианта никакого значения не имеет. 19 ноя 2019 в 15:49
  • @AnT , я сделал предположение, что автор не вполне понимает, что ему нужно, так как сам много лет преподавал олимпиадное программирование. Поэтому подсказал, что данную задачу следует решать не так, как в книжке. Такое часто бывает, что задаётся вопрос о том, как мне продолжать ездить на велосипеде без колёс, когда правильный ответ будет: установить колёса. Если автору мой ответ не нужен, он сам разберётся. Ну и потом, если кто-то будет искать алгоритм генерации подмножеств, найдёт этот вопрос и ему больше понравится именно мой ответ. Допускаете?
    – Zealint
    19 ноя 2019 в 15:58
  • а как быть если кол-во элементов исходного множества А больше чем размерность самого большого типа данных ?
    – ampawd
    24 ноя 2019 в 19:40
  • @ampawd , вы имеете в виду, что у вас нет доступа к переменным размером 32 бита? Потому что в этом случае уже 4 миллиарда подмножеств и реальные практические задачи (не олимпиадные), в которых нужно такое их количество, решаются принципиально иным способом, значительно более сложным, но и более эффективным, чем этот.
    – Zealint
    25 ноя 2019 в 1:22
  • Нет, допустим есть доступ к переменным всех размеров, я лишь хотел отметить, что это решение не является универсальным, так как ограничено размерностью переменной...просто раз уж речь про эффективность зашла то перспективней было бы именно эти решения предоставлять, которые более интересны
    – ampawd
    25 ноя 2019 в 9:44
1

Нет условия, что повторяющихся элементов нет. Поэтому можно изменить таким образом. Теперь есть связь с элементами множества.

void search(vector<int> set, vector<int> subset, int n, int k){
if (k == n + 1){
    print(subset);
} else{
    subset.push_back(set[k]);
    search(set, subset, n, k+1);
    subset.pop_back();
    search(set, subset, n, k+1);
}}

int main() {
vector<int> set = {1, 2, 3, 1};
vector<int> subset;
search(set, subset, 3, 0);
return 0;}
1

Приведенный вами код предназначен для генерации набора индексов элементов подмножества. Пользуясь индексами в векторе subset вы уже будете осуществлять доступ к вашему "множеству" (подразумевая, что множество представлено неким массивом) и обрабатывать его одному вам известным способом.

То есть для этого алгоритма совершенно не важно, что хранится в вашем множестве и как вы будете обрабатывать подмножества. Приведенный алгоритм от этого полностью абстрагирован. Он лишь генерирует наборы индексов для вас, а все остальное - ваша задача. Поэтому в нем и "нет обращения к элементам множества". Это вы должны дописать в него сами.

Если вы в качестве "множества" будете использовать четырехэлементный набор { 1, 2, 3, 1 }, то для алгоритма это просто упорядоченный четырехэлементный набор, ничем не отличающийся от { "вася", "коля", "миша", "лена" }. Алгоритм будет исправно генерировать "подмножества" для этого множества, как и для любого другого набора размера 4. Разумеется, с точки зрения этого подхода две 1 в вашем наборе считаются "разными".

0

Полное решение на с++

using namespace std;
typedef vector<int> vi;
#define PB push_back

void search(int k, int n,vi subset){
   if (k == n+1){
    for(int i = 0 ; i < subset.size(); i++){
        cout << subset[i] << " ";
    }
    cout << endl;
    subset.resize(0);
   }
   else{
    subset.PB(k);
    search(k+1,n,subset);
    subset.pop_back();
    search(k+1,n,subset);
   }


}

int main(){
   ios::sync_with_stdio(0);
   cin.tie(0);
   vi subset;
   int n,k;
   n = 3;
   k = 1;
   search(k,n,subset);
   return 0;
}
1
  • добро пожаловать на Stack Overflow на русском! пожалуйста, постарайтесь оставлять чуть более развёрнутые ответы. дополнить ответ можно, нажав править 11 июл 2021 в 15:57

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.