問題タブ [set-union]

この投稿の読者の皆様へ

Python で効率的に 2 つのリストの和集合のシーケンスを形成する方法を知っていますか? 次の 2 つのリストがあるとします。

そして私は計算したい：

これまで、次のループを使用しています。

しかし、私はこれが醜いと思います。私は2つのループが好きではありません。代わりに関数を使用することを好みます。

目的のタスクを達成するための別のアイデアはありますか? （とりわけ、Pythonの提案で一連のリストのデカルト積を取得しようとしましたが、役に立ちませんでした。）

どんな提案にも感謝します！

よろしく、 ファビアン

std::set_union<...> アルゴリズムのカスタム特殊化の次の例があります。http://en.cppreference.com/w/cpp/algorithm/set_unionからの実装を適応させました。

実装をカスタマイズする必要があるのは、両方のセットから要素のペアを作成したいからです。範囲がオーバーラップする (交差) 場合、出力には std::pair<*first_iter, *second_iter> が含まれます。

要素が最初のセットに一意である場所では、出力は概念的に std::pair<*first_iter, second_type()> になり、最後に要素が 2 番目のセットに一意である場所では、出力は std::pair になります。 .

コードは機能しますが、私のカスタマイズでは、 std::pair<> のいずれかの側の構成要素をデフォルトにするために LoadableFile 型をハードコーディングする必要がありました (上記の特殊化の 3 つのケースのうちの 2 つに応じて)。Merge テンプレート引数から型情報にアクセスしてその型を知る方法はありますか (それはPairMaker < Loadable, Loadable >であり、特殊化をハードコーディングすることなくデフォルト コンストラクト Loadable() ですか?

これは私のカスタマイズです：

OutputIt に適した要素を作成するために必要なフレームワークを提供するために、次のように、OutputIt に適したペアを作成する Merge クラスがあります。

私の場合、実際に特殊化を使用するには、次のように呼び出します。

C++ で STL を使用して、複数のベクトルをマージして、入力ベクトル内の要素の結合である結果のベクトルを作成しようとしています。各入力は既にソートされており、要素は unsigned short です。

「Expression: vector iterator + offset out of range」というエラーが表示されますが、その理由がわかりません。これは、Visual Studio 2013 デバッガーで実行されるデバッグ ビルドです。

コードは次のとおりです。

その意図は、各スキャン (sc) からの波長のベクトルがベクトル wl にマージされることです。(ベクトル wl は、ここには示されていないコードによって unsigned short の C++ 配列にコピーされます)。

コード例は千の言葉に値するので、それから始めます。

このコードはリストを取り、すべての要素を合計してそれらすべての合計を取得します (これの効率にも興味があります)。testSet の出力は次のとおりです。

これらのリストの和集合を見つけたい(セットにするため)が、次のように感じます:

パフォーマンスが低下します (実際のリストは数千の要素になります)。

これは正しい解決策ですか、それとも明らかな何かが欠けていますか?

2 つのデフォルト辞書の和集合を作成しようとしています。私のクラスのメソッドのコードは次のとおりです。

2 つのデフォルト辞書を作成します。

結果として

結合後の要素の合計数でなければなりません..

これは私が取得し続けるエラーです:

新しいコードは次のとおりです。

SML でセットを操作するために使用できる 3 つの関数定義を作成しようとしています。ご覧のとおり、実装はリストに基づいています。

Union は、 Set s と Set t の両方のすべての要素のセットです。(重複は不可)

交差は、要素が Set s と Set t の両方の一部であるセットです。

Set と Set t がセットの場合、Set t 内の Set の相対的補数は Set t 内の要素のセットですが、Set 内の要素のセットではありません。

現在、コードは次のようになっています。

ご覧のとおり、必要に応じて使用できる 2 つのヘルプ関数があります。mem と filter.filter はリストを調べて、ブール関数 p を満たす要素のみを保持しますが、mem はリストに値 a が含まれているかどうかを確認するだけです。 .

この質問がここに属していない場合は申し訳ありません。私の問題はコードではなく、アルゴリズムにあるため、別の Web サイトに適している可能性がありますが、stackoverflow の善良な人々は決して私を失望させませんでした。

質問は次のとおりです。

2 つの並べ替えられた配列が与えられA、Bそれらが同じ数の要素を持ち、それらがn要素を共有せず、同じ配列に要素が 2 回出現しないように、対数時間の複雑さで配列の和集合の中央値を見つけます。 .

非常に重要な注意:nが奇数の場合、中央値は中央の要素です。しかし、nが偶数の場合、中央値は中間要素の平均ではありません。中間要素の最小値として定義されます。

解決策: アイデアは非常に単純です。それらはソートされているため、 (と呼ばれる) の中央値と (と呼ばれる)のA中央値を で見つけることができます。の場合、和集合の中央値は の要素であることがわかります より小さいか、または の要素は よりも大きく、その逆の場合. したがって、冗長な要素を捨てて、 と がそれぞれ 2 つの要素で十分に小さくなるまで、同じプロセスを実行します。その後、これら 4 つの数値の間の中央値を見つけるだけで済みます。4 は偶数であるため、4 の数値の中央値は 2 番目の最小値になります。med1Bmed2O(1)med1>med2Amed1Bmed2med2>med1ABO(1)

これは私のコードです

意図したとおりに動作し、コンパイルされます。私が言ったように、問題は私のコードではなく、アルゴリズムにあります。問題を示す例を見てみましょう。

入力がA=[1,3,5]と であるとしB=[2,4,6]ます。そして。med1=3_ med2=4冗長な要素を捨てると、 と ができA=[3,5]ましB=[2,4]た。全体で 4 つの要素しかありません。データは十分に小さいので、これら 4 つの数値の中央値を見つけてください[3,5,2,4]。中央値は になります。これはと3の結合の中央値の正しい結果でもあるため、結果は正しいです。AB

A=[1,3,5,7]ここで、入力がと であると仮定しましょうB=[2,4,6,8]。med1=3とmed2=4。冗長な要素を捨てて getA=[3,5,7]とを取得しB=[2,4]ます。今med1=5とmed2=2。ここでも冗長性を捨てて getA=[3,5]およびを取得しB=[2,4]ます。これで、データは十分に小さくなりました。その中央値を求めると、[3,5,2,4]再び が得られ3ます。しかし、その結果は正しくありません。はと3の結合の中央値ではありません。正しい結果は になります。AB4

どうすればこの問題を解決できますか?