2

私が作成した小さなアプリケーションを使用すると、ユーザーは2つの配列にさまざまなアイテムを追加できます。一部のロジックは、各配列の内容から数値を計算します。

配列x内のすべてのアイテムは、配列yに配置したり、元に戻したりすることができます。配列yに属するアイテムは、移動できません（配列xから移動された場合を除く）。

ユーザーは、単純なjavascript uiを使用して、これらのアイテムを2つのリストで移動できます。物事を簡単にするために、私はもともと素朴なスクリプトを作成しました。

  1. アイテムをaからyに移動しました。
  2. この「可能性」を使用していくつかのロジックを実行しました
  3. 結果が以前よりも小さかった場合は、xをyのままにします。
  4. そうでない場合、xはxに残ります。
  5. xの次の項目に移動して、繰り返します。

私はこれが効果がないことを知っていました。私は読み回して、可能性または「順列」を覚えるためにビット単位の数学を使用してこれを行うように言われましたが、この段階でこの特定の問題を回避するのに苦労しています。

誰かが説明できれば（擬似コードは問題ありません）、次のことを達成するための最良の方法は何でしょうか。私は非常に感謝しています。

配列x=[100,200,300,400,500]配列y=[50,150,350,900]

これらの2つの配列を使用して、xの値ごとに、その値と他のすべての値のすべての組み合わせをxから配列yにプッシュします。それぞれについて、いくつかのロジックを実行します（つまり、テスト結果とこの「順列」を配列（xとyを表す2つの配列のオブジェクト）に格納します）。これは、大きな配列では非常に高価であり、多くのことを繰り返す可能性が高いと予測しています。組み合わせ。私はほとんどそこにいるように感じますが、この最後の段階で失われました。

長い説明でごめんなさい、そして事前に感謝します！

4

1 に答える 1

1

これを使用して、次のべき集合を作成しxます。

function power(x, y) {
    var r = [y || []], // an empty set/array as fallback
        l = 1;
    for (var i=0; i<x.length; l=1<<++i) // OK, l is just r[i].length, but this looks nicer :)
        for (var j=0; j<l; j++) {
            r.push(r[j].slice(0)); // copy
            r[j].push(x[i]);
        }
    return r;
}

使用法：

> power([0,2], [5,6])
[[5,6,0,2], [5,6,2], [5,6,0], [5,6]]

可能性または「順列」を覚えるためにビット単位の数学を使用してこれを行うように言われましたが、この段階でこの特定の問題に頭を悩ませることに苦労しています。

アイテムをサブセットに含めるかどうかを決定するために単一ビットを使用して、 2 n （長さnの配列の場合）まで反復します。配列の例[a、b]：

i   binary   included in set
-----------------------------
0   00       {      }
1   01       {    b }
2   10       { a    }
3   11       { a, b }

JSでは、最大31項目の配列にビット演算子を使用できます（これで十分です）。

function power(x, y) {
    var l = Math.pow(2, x.length),
        r = new Array(l);
    for (var i=0; i<l; i++) {
        var sub = y ? y.slice(0) : [];
        for (var j=0; j<x.length; j++)
            // if the jth bit from the right is set in i
            if (i & Math.pow(2,j)) // Math.pow(2,j) === 1<<j
                sub.push(x[j]);
        r[i] = sub;
    }
    return r;
}
于 2013-03-26T23:59:23.543 に答える