[Занимательные задачки, Программирование, C++, Алгоритмы] Обобщение классической задачи на множества с собеседований

Автор Сообщение
news_bot ®

Стаж: 6 лет 3 месяца
Сообщений: 27286

Создавать темы news_bot ® написал(а)
10-Сен-2020 11:30

Приветствую всех!
Я Олег. Специализация: C++/C/OS kernels/drivers/железки/сети/embedded. Около полутора лет живу и работаю за границей. Сейчас в Финляндии, перед этим была Польша. Об особенностях переезда в обе страны здесь рассказали до меня, кому интересно — пишите лично, на вопросы отвечу. О жизни в обеих странах здесь также написано немало. А вот свои впечатления от обеих в форме вольного эссе когда нибудь изложу.
Сейчас хочется рассказать о проблеме, на решение которой затратил половину дня, хотя она того не стоила. И самое смешное, что классический вариант этой задачи я однажды решал online на собеседовании. Столкнулся я с ней при копании одного из домашних проектов.
Итак, дано некое количество множеств целых чисел разного размера. Нужно найти числа, которые есть во всех множествах, кроме одного. Дубликаты по положению игнорируются.
Последнюю фразу поясню. Предположим, имеется множества {1, 2, 3}, {3, 0, 4}, {5}. В данном искусственном примере на роль находки претендует элемент {3}, имеющийся в нулевом и первом множествах и отсутствующий во втором. Записать это можно также в виде множества {3, 0, 1, 2}. Буквально эта запись расшифровывается так: значение 3 имеется во множествах с индексами 0, 1, и отсутствует во множестве 2. Множество {3, 1, 2, 0} считается эквивалентным вышеприведённому и игнорируется.
Принципиально это и есть обобщение классической задачи с собеседований. Формулируется последняя так: на вход некоего блока программы поступают числа, необходимо отсечь дубликаты. Решается элементарно с помощью примитива STL unordered_set. Он хорош тем, что при коротких числовых последовательностях обладает O(1) — постоянным временем поиска. В рамках ограниченной задачи он вполне себе приятен на вкус и цвет. К тому же, при добавлении в него дубликата, он просто его не добавит. Проверять возвращаемое значение в том случае также не надо. То есть, имеем экономию в три строки кода, которые по любому содержатся в имплементации шаблона.
Для простоты положим число множеств равным 3. Множества хранятся в векторах, или STL шаблоне vector.
Заполнение есть элементарная операция, и сопровождать её куском кода незачем. А вот дальше будет несколько интереснее.
// предположим, на входе в блок программы имеем 3 вектора целых чисел
// vector<int> own, two, three;
// некий объект, умеющий обращаться по индексу к любому из set
vector<unordered_set<int > > common(3);
// заполнили все set из векторов
unordered_set<int> all;
// здесь храним результаты
unordered_set<vector<int> > result;
for(auto cur : all)
{
    // временная переменная, хранящая результат итерации
    vector<int> cres(4);
    cres[0] = cur; // исходное значение
    for(auto j(0), i(1); j < common.size(); ++j, ++i)
    {
        cres[i] = (common[j].find(cur) == common[j].end() ? -1 : j);
        // значение есть в текущем set  ставим индекс set, нет - ставим -1
    }
    // считаем количество -1 в текущей итерации
    unsigned cnt(count(cres.begin(), cres.end(), -1);
    if(1 == cnt) // дальнейшее если числа нет только в одном множестве
    {
        // код поиска индекса множества, где элемента нет, не привожу, он элементарен. Предположим, он найден, и поставлен на последнее место в cres
       // На 1-м и 2-м тогда находятся индексы множеств, где элемент есть
        if(result.find(cur) == result.end()) // первая проверка на дубликат
        {
             swap(cur[1], cur[2]);
             // здесь проверка не нужна, set сделает её за нас
             cres.insert(cur);
        }
    }
}

1) В all кладём содержимое всех трёх векторов
2) В common по очереди, согласно индексам, заполняем каждый отдельный set для каждого vector
Выглядит это так:
// общее хранилище для всех векторов
vector<int>* storage{&own, &two, &three};
for(unsigned i(0); i < common.size(); ++i)
{
    fill_Storage(common[I], storage[I]);
}
// само заполнение тривиально - простой перебор vecotr с добавкой элемента в unordered_set

3) Делаем цикл по всем элементам all
4) cres есть результат текущей итерации. Он имеет такой формат:
элемент из all, индекс вектора в common, индекс вектора в common, индекс вектора в common
5) В cres[0] кладём текущий элемент из common
6) Перебираем все set в common
7) На каждом шаге спрашиваем у текущего set в common, есть ли у него такой элемент, если есть, заполняем индекс, если нет, то -1
8) У элементов, попадающих под наши условия, cres должен содержать одну -1
9) На последнем месте в cres должен лежать индекс set, в котором элемент отсутствует. Это несложно, но загромождать код не хочу. Кому интересно — пишите в личку, расскажу.
Вот и все, полдня мучений. Код на красоту не претендует. Желание было только изложить идею, или подход к решению подобного рода задач.
Количество множеств, равное 3 общается на большее число. Тогда придётся иметь ещё один set или map, в который складываются все дубликаты. Дубликаты на каждой итерации придётся получать алгоритмом weave, или плетения. Для особо интересующихся рекомендую посмотреть книгу Гейл Лакман Мак-Дауэлл"Карьера программиста"издание 6 или 7.
Там этот алгоритм изложен как часть решения одной конкурсной задачи.
Суть его проста: выдергивается начальный элемент списка и по очереди засовывается между соседними. Цикл заканчивается когда все элементы перебраны. Если кого то интересует электронная версия книги, в её в интернете много. Кому надо — пишите, 6-е издание есть, выложу.
===========
Источник:
habr.com
===========

Похожие новости: Теги для поиска: #_zanimatelnye_zadachki (Занимательные задачки), #_programmirovanie (Программирование), #_c++, #_algoritmy (Алгоритмы), #_c++11, #_zanimatelnye_zadachki (
Занимательные задачки
)
, #_programmirovanie (
Программирование
)
, #_c++, #_algoritmy (
Алгоритмы
)
Профиль  ЛС 
Показать сообщения:     

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

Текущее время: 18-Май 11:20
Часовой пояс: UTC + 5