Вывод списка определенных подмножеств с использованием STL - PullRequest
Новая
       13

Вывод списка определенных подмножеств с использованием STL

0 голосов
/ 21 июля 2011

Скажем, у меня есть диапазон чисел, скажем, {2,3,4,5}, сохраненный в этом порядке в std::vector v, и я хочу перечислить все возможные подмножества, которые заканчиваются на 5 с использованием STL ... то есть: 

2 3 4 5
2 3 5
2 4 5
3 4 5
2 5
3 5
4 5
5

(надеюсь, я ничего не забуду :))

Я пытался использовать while(next_permutation(v.begin(),v.end())), но не нашел желаемого результата:)

У кого-нибудь есть идея?

PS: те, кто делал архивы google code jam 2010, могут это узнать:)

Ответы [ 4 ]

6 голосов
/ 21 июля 2011

Давайте сосредоточимся на проблеме печати всех подмножеств. Как вы знаете, если у вас есть вектор n элементов, у вас будет 2^n возможных подмножеств. Неслучайно, если у вас есть n -битное целое число, максимальное сохраненное значение равно 2^n. Если вы рассматриваете каждое целое число как вектор битов, то итерирование по всем возможным значениям даст все возможные подмножества битов. Ну, у нас есть подмножества бесплатно, итерируя целое число!

Предполагая, что вектор содержит не более 32 элементов (более 4 миллиардов возможных подмножеств!), Этот фрагмент кода напечатает все подмножества вектора v (исключая пустой): 

for (uint32_t mask =1; mask < (1<<v.size()); ++mask)
{
  std::vector<int>::const_iterator it = v.begin();
  for (uint32_t m =mask; m; (m>>=1), ++it)
  {      
    if (m&1) std::cout << *it << " ";
  }
  std::cout << std::endl;
}

Я просто создаю все возможные битовые маски для размера вектора и перебираю каждый бит; если он установлен, я печатаю соответствующий элемент.

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

Я эффективно использую std::vector, const_iterator и std::cout, так что вы можете подумать, что это решается с помощью STL. Если я придумаю что-нибудь более STLish, я дам вам знать (ну, но как, это просто повторение). Вы можете использовать эту функцию в качестве эталона для ваших решений STL, хотя; -)

РЕДАКТИРОВАТЬ: Как отметил Йорген Фог, он не решает ваши подмножества блюза, если вы хотите работать с большими векторами. На самом деле, если вы хотите распечатать все подмножества для 32 элементов, он будет генерировать терабайты данных. Вы можете использовать 64-битное целое число, если вы чувствуете себя ограниченным константой 32, но вы даже не закончите итерацию по всем числам. Если ваша проблема состоит в том, чтобы просто ответить на количество желаемых подмножеств, вам определенно нужен другой подход. И STL тоже не сильно поможет; -)

1 голос
/ 21 июля 2011

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

void subsets(std::set<std::set<int>> &sets, std::set<int> initial)
{
    if(initial.empty())
        return;

    sets.insert(initial);//save the current set in the set of sets

    std::set<int>::iterator i = initial.begin();
    for(; i != initial.end(); i++)//for each item in the set
    {
        std::set<int> new_set(initial);//copy the set
        new_set.erase(new_set.find(*i));//remove the current item
        subsets(sets, new_set);//recursion ...
    }
}

sets - это набор, который содержит все нужные вам подмножества.initial - это набор, для которого вы хотите иметь подмножества.Наконец, вызовите это с помощью subsets(all_subsets, initial_list_without_5);

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

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

0 голосов
/ 22 июля 2011

Томаш описывает решение, которое будет работать до тех пор, пока n<=32, хотя для печати 2 ^ 32 различных подмножеств потребуется очень много времени. Поскольку границы для большого набора данных равны 2 <= n <= 500, генерируя все подмножества, это определенно не тот путь. Вам нужно придумать какой-нибудь умный способ избежать их генерации. На самом деле, в этом весь смысл проблемы. </p>

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

0 голосов
/ 21 июля 2011

использовать перестановку для создания вектора векторов.Затем используйте std :: partition с функцией, чтобы отсортировать ее по векторам, которые заканчиваются на 5, и тем, которые не имеют.

...