0

私は一般的なケースのアルゴリズムを知っています (たとえば、一度に m を取得した n 要素のすべての組み合わせを生成する) が、m=n-1 のケース用に特別に設計されたより高速なアルゴリズムがあるかどうか疑問に思っていました。また、そのようなアルゴリズムが存在する場合、誰かが C/C++ 実装を指摘できますか?

4

2 に答える 2

4

それはとても簡単です - シンプルなサイクルを使ってすべての要素を繰り返します。このサイクルでは、1 つ (サイクル内のインデックスによって指されているもの) を除くすべての要素からなる新しいセットを構築します。

O(N)注：複雑さを達成できるように、いくつかの注意事項があります（C++例を使用しますが、ベクターのようなコンテナで他の言語を使用することもできます）。

In C++:vector<int> aすべての数値を保持する があると仮定します:

vector<int> a;
... initialize a ....
vector<int> b(a.begin()+1, a.size()); // Now b will have all elements of a but the first one.

for (int i=0;i<a.size() - 1;++i) {
  b.push_back(a[i]);
  swap(b[i], b[b.size()-1]);
  b.pop_back();
}

上記のコード b を使用すると、すべての組み合わせが順次反復されます。

于 2013-03-15T11:44:47.733 に答える
0

セットがある場合

  • 2 要素 {1,2} サブセットには 2^2 要素 {}、{1}、{2}、{1,2} があります
  • 3 つの要素 {1,2,3} サブセットには 2^3 要素があります {}、{1}、{2}、{3}、{1,2}、{1,3}、{2,3}、{ 1,2,3}
  • 4 要素 {1,2,3,4} サブセットには 2^4 要素があります {}、{1}、{2}、{3}、{4}、{1,2}、{1,3}、{ 1,4}{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3 ,4},{1,2,3,4}

したがって、上記のセットは2つのループを使用して達成できると思います

コンビネーションでも

U を要素数 n の集合とする。ちょうど j 個の要素を持つ集合 U の個別の部分集合の数を数えたいとします。これは N!/J! と書くことができます。*(ニュージャージー州)!

注: 空の要素サブセットを削除すると、式は 2^n-1 になります

これが私の答えです。

  • N=2 の場合 {1},{2}
  • N=3 の場合、N=2 要素 {1,3}{2,3} の末尾に 3 を追加し、N=2 要素 {1,2} を混合します
  • N=4 の場合、N=3 要素 {1,3,4}{2,3,4} {1,2,4} の最後に 4 を追加し、N=3 要素 {1,2,3} を混合します。

お役に立てれば！！！

于 2013-03-15T14:46:35.160 に答える