Минимальное разбиение вектора объектов (C++)

У меня есть std::vector объектов, где каждый элемент вектора более или менее выглядит так:

struct Obj {
  int group;
};

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

Можно ли обойтись без итерации по каждой перестановке вектора и просмотра количества разделений в каждой перестановке?

редактировать:

Был задан пример, поэтому я попытаюсь привести его.

Если начальный вектор объектов был

[ {1}, {2}, {3}, {2}, {3}, {1}, {4}, {5}, {3}, {2} ]

Оптимальным разделением было бы разделить его на три раздела следующим образом:

[ {1}, {2}, {3}, {4}, {5} ] [ {1}, {2}, {3} ] [{2}, {3} ]

Так что в каждом разделе все записи принадлежат к другой группе.

Источник

2 ответа

Решение

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

В псевдокоде для входного вектора v размера n:

  • инициализировать пустую гистограмму H
  • для каждого элемента x в v:
    • увеличиваем H [ x ] на единицу, инициализируем его нулями раньше, если такого бина уже нет
  • м ← максимальная частота в H
  • инициализировать пустые векторы v 1,…, v m
  • для каждого значения x были H [ x ] ≥ 0:
    • для i ← 1 до H [ x ]:
      • добавить х к V я

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

  • инициализировать пустую гистограмму H
  • для каждого элемента x в v:
    • увеличивайте H [key (x) ] на единицу, обнуляя его до того, если такого бина нет
  • м ← максимальная частота в H
  • инициализировать пустые векторы v 1,…, v m
  • для каждого значения x в v:
    • я ← H [ключ (х) ]
    • добавить х к V я
    • уменьшить H [ключ (x) ] на единицу

Если вы хотите быстрое решение, вы можете использовать std::unordered_map<int, int> для вашей гистограммы.

Вот как (в конечном счете, несколько чрезмерно обобщенная) реализация может выглядеть в C++14.

#include <algorithm>            // std::max_element
#include <functional>           // std::hash, std::equal_to
#include <iterator>             // std::iterator_traits
#include <unordered_map>        // std::unordered_map
#include <vector>               // std::vector

template<typename FwdIterT,
         typename ValueT = typename std::iterator_traits<FwdIterT>::value_type,
         typename ValueHashT = std::hash<ValueT>,
         typename ValueEqCmpT = std::equal_to<ValueT>>
decltype(auto)
min_partition(const FwdIterT begin, const FwdIterT end)
{
  std::vector<std::vector<ValueT>> partitions {};
  std::unordered_map<ValueT, int, ValueHashT, ValueEqCmpT> histo {};
  for (auto iter = begin; iter != end; ++iter)
    histo[*iter]++;
  const auto cmpfreq = [](const auto& lhs, const auto& rhs){
    return lhs.second < rhs.second;
  };
  const auto maxbin = std::max_element(histo.cbegin(), histo.cend(), cmpfreq);
  partitions.resize(maxbin->second);
  for (auto iter = begin; iter != end; ++iter)
    partitions.at(histo.at(*iter)-- - 1).push_back(*iter);
  return partitions;
}

Это можно использовать так.

#include <iostream>             // std::cout
#include <string>               // std::string
#include <utility>              // std::begin, std::end

int
main(int argc, char * * argv)
{
  using std::begin;
  using std::end;
  for (int i = 1; i < argc; ++i)
    {
      const std::string text {argv[i]};
      const auto partitions = min_partition(begin(text), end(text));
      std::cout << "input:  " << text << "\n";
      std::cout << "output: " << partitions.size() << " partitions\n\n";
      for (auto it1 = begin(partitions); it1 != end(partitions); ++it1)
        {
          std::cout << "[";
          for (auto it2 = begin(*it1); it2 != end(*it1); ++it2)
            std::cout << (it2 != begin(*it1) ? ", " : "") << *it2;
          std::cout << "]\n";
        }
      if (i != argc - 1)
        std::cout << "\n\n";
    }
}

Если в качестве входных данных даны некоторые известные строки, он выдаст следующий вывод.

input:  WEWEREARRESTEDAFTERDADATEDEEREGGS
output: 10 partitions

[W, F, A, T, D, R, E, G, S]
[W, S, T, R, A, D, E, G]
[R, T, A, D, E]
[A, R, D, E]
[R, E]
[E]
[E]
[E]
[E]
[E]


input:  ALASDADHADAGLASSSALAD
output: 8 partitions

[H, G, S, L, A, D]
[D, L, S, A]
[L, D, A, S]
[S, D, A]
[A]
[A]
[A]
[A]


input:  THEQUICKBROWNFOXJUMPSOVERTHESLEAZYDOG
output: 4 partitions

[Q, I, C, K, B, W, N, F, X, J, U, M, P, V, R, T, H, S, L, E, A, Z, Y, D, O, G]
[T, H, U, R, S, O, E]
[O, E]
[E, O]
Источник

Самым простым способом для этого, вероятно, будет следующий алгоритм (псевдокод):

std::vector<std::vector<Obj>> partitions;
sort(yourVector);
for (each group of equal Obj) {
    if(sizeOfThisGroup > partitions.size())
        add enough partitions
    split the group into the partitions
}

Это работает в O(nlog(n)), Если самое большее m Obj равны, вы в конечном итоге m перегородки. Это очевидно минимально.

Источник
Другие вопросы по тегам