2

2つのデータセットがあり、各エントリが重みで構成されているとします。各セットは、重量の昇順で並べられています。いくつかのサンプルセットをリストします。

Set 0: {4, 8, 19, 25, 25, 26}    
Set 1: {1, 2, 3, 8, 20, 27}

これらの2つのセットの間で可能なすべてのペアを見つけたいのですが、それらのペアを合計された重みの小さいものから大きいものの順に見つけたいと思います。したがって、4 + 1、4 + 2、4 + 3、8 +1などです。セットはc++std::multisetであると想定できますが、それを超えると、どの言語でも同じになると思います。

ここで、2つのイテレータを使用して、最初のペアを1秒ごとに順番に繰り返すことなどを考えましたが、この例ではSet 0: 4+ Set 1: 8> Set 0: 8+なので、合計された最小の重みから順に各ペアを計算しません。Set 1: 1結果をいつでも並べ替えを行うコンテナにダンプできますが、それは非効率的なようです。これを実行できるかどうかに依存する他の最適化もあります。最後に余分な並べ替えを行わずにこれを行うための賢い方法はありますか？

編集：可能なすべてのペアリングを取得する必要があるため、最小の合計を取得するために1つのイテレータまたは他のイテレータをインクリメントするほど簡単ではありません。それはペアのほとんど（半分？）を逃します。ある種のイテレータスタックを使用しているかもしれませんが...

4

2 に答える 2

2 
#include <iostream>
#include <set>
#include <vector>
#include <limits>

std::multiset<int> set1 {4, 8, 19, 25, 25, 26};
std::multiset<int> set2 {1, 2, 3, 8, 20, 27};

int main()
{
  std::vector<std::pair<std::multiset<int>::const_iterator,
    std::multiset<int>::const_iterator>> setIterators;
  for (auto i = set1.begin(); i != set1.end(); ++i)
    setIterators.push_back(std::make_pair(i, set2.begin()));

  for (std::size_t count = set1.size() * set2.size(); count != 0; --count)
  {
    int minValue = std::numeric_limits<int>::max();
    auto minElement = setIterators.begin();
    for (auto i = setIterators.begin(); i != setIterators.end(); ++i)
    {
      if (i->second == set2.end())
        continue;
      int sum = *i->first + *i->second;
      if (sum < minValue)
      {
        minValue = sum;
        minElement = i;
      }
    }
    std::cout << *minElement->first << " + " << *minElement->second << " = " <<
      minValue << std::endl;
    ++minElement->second;
  }
  return 0;
}

出力：

$ g++ -std=c++11 main.cpp -o main && ./main
4 + 1 = 5
4 + 2 = 6
4 + 3 = 7
8 + 1 = 9
8 + 2 = 10
8 + 3 = 11
4 + 8 = 12
...
26 + 27 = 53
于 2012-10-12T19:30:24.873 に答える
2

2つのソートされたリストA（サイズm）とB（サイズn）を示します。

アルゴリズム：

  1. すべてのi=0からn-1についてA[0]とB[i]の合計を計算します。リストAから合計に含まれる要素を特定する必要があります。1つの方法は、インデックスを添付することです（すべての合計で0です）。ここ）。すべてのペアを、合計順に並べられた最小ヒープにプッシュします。
  2. ヒープをポップし、合計を取り出します。添付のインデックスを使用して、リストAの次の要素との合計を計算します。インデックスがすでにm-1の場合は、何もする必要はありません。それ以外の場合は、インデックスをインクリメントしてヒープにプッシュバックします。
  3. ヒープが空になるまで（すべてのm * n値に対して）ステップ2を繰り返します。

ステップ1はO（n log n）になります。

ステップ2は、ヒープのサイズが減少し、決して増加しない可能性があるため、最大でO（log n）です。ステップ2をm*n回繰り返すと、O（mn log n）の時間計算量になります。

全体的な複雑さはO（mn log n）です。

上記のアルゴリズムでリストBとして小さいリストを使用することにより、時間計算量をわずかに改善できます（大きなヒープではなく、小さなヒープを管理するだけで済みます）。

std::priority_queue（Stackerによる）を使用した実装：

#include <iostream>
#include <set>
#include <queue>
#include <limits>

std::multiset<int> set1 {4, 8, 19, 25, 25, 26};
std::multiset<int> set2 {1, 2, 3, 8, 20, 27};

struct Node
{
  Node(std::multiset<int>::const_iterator set1Iterator, int set2Value) :
    set1Iterator(set1Iterator),
    set2Value(set2Value),
    sum(*set1Iterator + set2Value)
  {
  }

  bool operator < (const Node& other) const
  {
    return sum > other.sum; // Reverse order as std::priority_queue sorts for the greatest value
  }

  std::multiset<int>::const_iterator set1Iterator;
  int set2Value;
  int sum;
};

int main()
{
  std::priority_queue<Node> heap;
  for (auto i = set2.begin(); i != set2.end(); ++i)
    heap.push(Node(set1.begin(), *i));

  while (!heap.empty())
  {
    Node min(heap.top());
    heap.pop();

    std::cout << *min.set1Iterator << " + " << min.set2Value << " = " <<
      min.sum << std::endl;
    if (++min.set1Iterator != set1.end())
    {
      min.sum = *min.set1Iterator + min.set2Value;
      heap.push(min);
    }
  }
  return 0;
}
于 2012-10-12T19:51:52.613 に答える