3

値の配列が完全に入力されているので、この配列から要素を任意に削除し、遠端に向かってさらに削除したいと思います。

たとえば、与えられた入力（ここで、。は入力されたインデックスを示します）

............................................

何か欲しいのですが

....... . ...  .. .  .  ..    .          .

私の最初の考えは、要素を数え、次に配列を反復処理して、現在のインデックスと配列の合計サイズの間のどこかに乱数を生成することでした。例：

if ( mt_rand( 0, $total ) > $total - $current_index ) 
    //remove this element

ただし、これにはループが一周するたびに乱数を作成する必要があるため、非常に困難になります。

これを行うためのより良い方法はありますか？

4

3 に答える 3

2

簡単な方法の1つは、エントリごとに重み付きコインを裏返し、コインを最後に向かってより重みを付けて裏返すことです。たとえば、配列のサイズがnの場合、エントリごとにからからの乱数を選択し0、n-1インデックスが乱数以下の場合にのみ値を保持できます。（つまり、各エントリを確率で保持し1 - index/totalます。）これには、配列をとにかく圧縮する場合に、十分で効率的な乱数ジェネレーターを使用しているという優れた利点があります（単純な整数ハッシュである可能性があります）。ナンス）、メモリアクセスにはかなり高速になります。

一方、いくつかの項目を空白にしているだけで、配列を再配置していない場合は、インデックスの終わりに近い数値を選択することが多い、ある種の加重乱数ジェネレーターを使用できます。たとえば、[0,1]の値でfloatを生成する乱数ジェネレーターがある場合（閉じた境界または開いた境界はそれほど重要ではありません）、そのようなランダムなfloatrを取得して2乗することを検討してください。これは、より低い値を好む傾向があります。あなたはそれをひっくり返すことによってこれを修正することができます：1-r^2。もちろん、これはからのインデックス範囲内にある必要がある0のでn - 1、を取りfloor(n * (1 - r^2))、またnに切り捨てn-1ます。

これらの手法の両方には、事実上無限の数のバリエーションがあります。

于 2012-05-29T14:05:34.640 に答える
2

これはおそらくこれを行うための最良/最も効率的な方法ではありませんが、私が思いつくことができる最良の方法であり、機能します。

注意：コードパッドの例は実行に時間がかかりますが、これは、最後に追加したきれいな印刷ループが原因で、視覚的に機能していることがわかります。内部ループを削除すると、実行時間は許容レベルまで低下します。

<?php

  $array = range(0, 99);

  for ($i = 0, $count = count($array); $i < $count; $i++) {

    // Get array keys
    $keys = array_keys($array);

    // Get a random number between 0 and count($keys) - 1
    $rand = mt_rand(0, count($keys) - 1);

    // Cut $rand elements off the beginning of the keys
    $keys = array_slice($keys, $rand);

    // Unset a random key from the remaining keys
    unset($array[$keys[array_rand($keys)]]);

  }
于 2012-05-29T14:48:36.037 に答える
1

この方法はランダムではありません。関数とその逆を定義することで機能します。定数係数が異なるさまざまな関数は、さまざまな分布特性を持ちます。

連続関数を配列のような離散構造にマッピングすると予想されるように、結果は非常にパターンのようになります。

二次関数を使用した例を次に示します。定数を変えてみることができます。

デモ：http ：//codepad.org/ojU3s9xM

#as in y = x^2 / 7;
function y($x) {
    return $x * $x / 7;
}
function x($y) {
    return 7 * sqrt($y);
}

$theArray = range(0,100);
$size = count($theArray);

//use func inverse to find the max value we can input to $y() without going out of array bounds
$maximumX = x($size);
for ($i=0; $i<$maximumX; $i++) {
    $index = (int) y($i);

    //unset the index if it still exists, else, the next greatest index
    while (!isset($theArray[$index]) && $index < $size) {
        $index++;
    }

    unset($theArray[$index]);
}




for ($i=0; $i<$size; $i++) {
    printf("[%-3s]", isset($theArray[$i]) ? $theArray[$i] : '');
}
于 2012-05-29T15:22:55.870 に答える