Ещё одна задача на множества

cat * | uniq -u

Добрый день! Не до конца понятны условия задачи. Все найденные числа должны быть в одних и тех же множествах? Что если множество такое:

{{1, 2}, {2, 3}, {3, 4}}

Здесь выходит, что 2 есть в первом и втором векторе, а 3 во втором и третьем. Ну и мое решение на Wolfram

Как же неоптимально и сложно. Еще и куча ошибок. Все что надо — это для каждого числа подсчитать, в скольки множествах оно встречается и вывести те, где ответ n-1.

Я правда не понял, что у вас за "дупликаты" там. Если у вас есть "множество" {3, 0, 1, 2} (элемент 3 во множествах 0 и 1 но не 2), то не может быть "множества" {3, 1, 2, 0}, ведь 3 уже есть в 0-ом множестве!

Ваша же проверка на "дупликаты" в коде не работает никогда. Во-первых, там опечатка и вы меняете местами элементы в cur, хотя похоже подразумевалось cres. Во-вторых, первым элементом cres всегда будет число cur, которое уникально всегда, ведь это же элемент set! Поэтому проверки в result.find() у вас всегда вернут false. Еще у вас код result никогда не заполняет.

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

В итоге решение в k раз быстрее (если у вас k множеств и короче), да еще и работает:

vector<vector<int>> sets; // входные данные
unorderd_map<int, int> counts; // счетчики
unorderd_set<int> seen_numbers; // для дупликатов
vector<int> result; // ответ

for (size_t i = 0; i < sets.size(); ++i) {
  for (auto num : sets[i]) {
     // убрать, если дубликатов нет
     if (seen_numbers.find(num) != seen_numbers.end()) continue;
     seen_numbers.insert(num);

     counts[num]++;
  }
  seen_numbers.clear();
}
for (auto it : counts) {
  if (it.second + 1 == sets.size()) {
    result.push_back(it.first);
  }
}

def calc(sets):
    cnt = {}
    for s in sets:
        for el in s:
            cnt[el] = cnt.get(el, 0) + 1

    return list([el for el,c in cnt.items() if c == len(sets)-1])

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

Я вот про эту часть:

Последнюю фразу поясню. Предположим, имеется множества {1, 2, 3}, {3, 0, 4}, {5}. В данном искусственном примере на роль находки претендует элемент {3}, имеющийся в нулевом и первом множествах и отсутствующий во втором. Записать это можно также в виде множества {3, 0, 1, 2}. Буквально эта запись расшифровывается так: значение 3 имеется во множествах с индексами 0, 1, и отсутствует во множестве 2. Множество {3, 1, 2, 0} считается эквивалентным вышеприведённому и игнорируется.

В текущем решении вы перебираете все различные числа (до 64). Числа различные — первые элементы cres будут уникальными. cres вообще не нужен. Просто, если у вас cnt стал n-1 — то все, текущее число в ответ. Никаких повторений никак не может быть.

Во вторых, ваше решение до сих пор такое же неоптимальное, как в начале.
Вот вам аналогия: Задача подсчитать для каждого числа в массиве, сколько раз оно встречается в массиве. Правильное решение — пройтись по массиву и для каждого числа увеличить счетчик в массиве из 64 элементов. Ваше решение — пройтись по массиву и для каждого числа опять пройтись по массиву, и если числа совпали увеличить счетчик. Это аналогия. В вашей задаче не массив чисел, а массив множеств, но суть со вторым лишним вложенным проходом осталась.

Правильное решение тут завести один массив счетчиков на 64 элемента. Вместо построения битмапов — вам нужен один массив флагов на 64 элемента, который будет говорить, обработали ли вы число с таким значением в текущем множестве или нет. Если не обработали, делайте пометку в массиве флагов и увеличивайте счетчик.

Вот все решение (опять же, в 2 раза короче вашего и в 3 раза быстрее):

void PrepareData(const vector<vector<int> >& src, vector<int>& res)
{
  vector<int> cnt(MAX,0);
  for (const auto& cur_set : src) {
    int64_t was = 0;  // битмап для текущего множества.
    for (const auto& v : cur_set) {
      if ((was & (1 << v)) == 0) {
        was |= 1 << v;
        ++cnt[v];
      }
    }
    for (int i = 0; i < MAX; ++i) {
      if(cnt[i]+1 == src.size()) res.push_back(i);
    }
  }