首页 文章

最小划分对象向量(C)

提问于
浏览
1

我有一个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 回答

  • 3

    如果我正确理解您的要求,则“最小分区数”由原始向量中单个值的最大频率给出。因此,您可以创建一个直方图,然后在其中找到最大的条目。 (这与 vector.)的大小呈线性关系,现在创建 m 个矢量(其中 m 是刚刚确定的最大频率),并将 m 个相同的值分别分配给其中一个。保证您可以将其余元素分布在这样就不会在分区中出现重复项。

    在 pseudo-code 中,尺寸为 n 的 input-vector v:

    • 初始化一个空的直方图 H

    • 对于 v 中的每个项 x:

    • 将 H [1]加 1,如果尚无此类 bin,则将其 zero-initializing 递增

    • m←H 中的最大频率

    • 初始化空向量 v1,…,vm

    • 对于每个值 x 均为 H [2]≥0:

    • 因为我←1 到 H [3]:

    • 将 x 附加到 vi

    请注意,如果向量中的对象具有确定它们是否等于其唯一数据成员的键,则此方法很好用。但是,如果他们有更多的状态需要保留,但不参与确定平等性,则可以轻松调整此过程以解决这一问题。

    • 初始化一个空的直方图 H

    • 对于 v 中的每个项 x:

    • 如果尚无此类 bin,则将 H [4]加 1,然后 zero-initializing

    • m←H 中的最大频率

    • 初始化空向量 v1,…,vm

    • 对于 v 中的每个值 x:

    • 我←H [5]

    • 将 x 附加到 vi

    • 将 H [6]减一

    如果需要快速解决方案,可以将std::unordered_map<int, int>用作直方图。

    这就是(最终有点 over-generalized)实现在 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";
        }
    }
    

    如果给定一些 well-known 字符串作为输入,它将产生以下输出。

    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]
    
  • 2

    最简单的方法可能是以下算法(伪代码):

    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个分区。这显然是最小的。

相关问题