Все подмножества множества

Опубликовано Sep 30, 2011 в Массивы и строки | 5 коммент.

, , ,

Разработайте метод all_subsets, который бы смог вернуть все подмножества заданного множества. Возможная сигнатура метода приведена ниже. Ее можно изменить, если Вы найдете это нужным.

void all_subsets(const int* given_set, int size_given_set /*, ваши выходные параметры */)
{
  //ваш код
}

Критерии оценки:

Кандидат должен продемонстрировать видение разных вариантов организации данных и разных подходов к реализации, а также осознанного выбора между ними.

Ожидаемые вопросы:

  1. Можно ли использовать динамические контейнеры из STL?
  2. Можно/нужно ли использовать рекурсию?

Оценка результатов:

Задача предполагает создание большого количества динамических структур данных, поэтому применение контейнеров из STL напрашивается само собой, следовательно первый вопрос стоит задать. Положительный ответ на него весьма облегчит написание кода. Вопрос по поводу рекурсии вряд ли нужен. Рекурсия – стандартный прием, никто специально не ограничивает его применение, если оно целесообразно. Кроме того, любое рекурсивное решение можно перевести в итерационное, выполнив раскрутку стека рекурсии через циклы. Возможно, этот вопрос поднимет интервьюэр, когда ознакомится с Вашей реализацией. Тогда хорошо, если Вы видите альтернативный алгоритм и готовы обсуждать его достоинства и недостатки по сравнению с Вашим.
 

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

 

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

 


5 Коммент. : “Все подмножества множества”

  1. Федор says:
    #include "stdafx.h"
    #include <algorithm>
    #include <set>
     
    void all_subsets(int* given_set, int size_given_set, set<set<int>> &result)
    {
    	set<int> subset(given_set, given_set + size_given_set);
    	result.insert(subset);
    	if (size_given_set >= 1)
    	{
    		all_subsets(given_set, size_given_set - 1, result);
    		for (int i = 0; i < size_given_set; ++i)
    		{
     
    			std::swap(given_set[i], given_set[size_given_set - 1]);
    			all_subsets(given_set, size_given_set - 1, result);
    			std::swap(given_set[i], given_set[size_given_set - 1]);
    		}
    	}
    }
     
     
    int _tmain(int argc, _TCHAR* argv[])
    {
    int a[5] = { 1, 2, 3, 4, 5 };
    	set<set<int>> result;
    	all_subsets(a, 5, result);
    	for (set<set<int>>::iterator it = result.begin(); it != result.end(); ++it)
    	{
    		for (set<int>::iterator it2 = it->begin(); it2 != it->end(); ++it2)
    			cout << *it2 << " ";
    		cout << endl;
    	}
    	return 0;
    }

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

  2. Артём says:
    void all_subsets(const int* given_set, int size_given_set, set<set<int>> &result)
    {
    	int i, j, max;
     
    	for (i = 0, max = 1; i < size_given_set; ++i)
    		max *= 2;
     
    	for (i = 0; i < max; ++i)
    	{
    		set<int> subset;
     
    		for (j = 0; j < size_given_set; ++j)
    		if ((i >> j) & 1)
    			subset.insert(given_set[j]);
     
    		result.insert(subset);
    	}
    }

Оставить комментарий

Ваш адрес email не будет опубликован.


*