0

私は良い開発者の友達と興味深い議論をしました。与えられた配列値のランダムシーケンスを作成したかったのですが、最大の断片化があり、検出可能なパターンはありませんでした。このいわゆる最大ランダム性は、どの一意のシーケンスでも実質的に常に同じです。

入力配列の例：

array(1, 2, 3, 4, 5);

標準のrand（）関数の結果の例：

array(2, 3, 1, 5, 4);

上記の出力で私が気に入らないのは、「2、3」や「5、4」のようなシーケンス値です。十分に断片化されていません。

期待される結果は次のようになります。

array(3, 5, 1, 4, 2);

だから私の質問。最大のランダム性を計算するための、または単語のより良い選択のための最大の断片化のための既知の式はありますか？

4

4 に答える 4

2

つまり、ランダム化ではなく、ソートです。ランダム化の結果は、初期データの順序に依存するべきではありません。

この場合の断片化により、ソート前とソート後の配列の違いを理解する必要があります。ただし、タスクによって評価を変える必要があります。たとえば、要素の位置や順序の違いを評価できます。

ソート例。

    <?
// it must be uksort() function with sequence formula, but for me easier do like this
    $array = array(1, 2, 3, 4, 5);
    uk_sort($array);
    function uk_sort(&$array) {
        for($i=0;$i<count($array);$i++) {
            if($i%2==0) {
                $even[] = $array[$i];
            } else {
                $odd[] = $array[$i];
            }
        }
        $even[] = array_shift($even);
        rsort($odd);
        $array = array_merge($even, $odd);
    }
    print_r($array);
    ?>
Array
(
    [0] => 3
    [1] => 5
    [2] => 1
    [3] => 4
    [4] => 2
)
于 2012-06-06T12:56:04.163 に答える
2

リストを2つ（またはそれ以上）のコレクションに分割し、それらをシャッフルしてから順番にミックスすることができますか？

array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

array(1, 2, 3, 4, 5);
array(6, 7, 8, 9, 10);

array(2, 3, 1, 5, 4);
array(8, 7, 10, 9, 6);

array(2, 8, 3, 7, 1, 10, 5, 9, 4, 6)

これにより、かなり高い断片化が得られますが、最大ではありません。最大値を取得するには、さらに多くの作業が必要になると思います。

于 2012-06-06T13:02:00.827 に答える
1

これは、移動セールスマンタイプの問題のように聞こえると思います。「距離」は、選択した2つのエントリの差です。ただし、目標は、合計距離を最小化するのではなく、最大化することです。

私は実際にこのトピックについて多くのことを知りませんが、私が知っていると思うことは次のとおりです。

巡回セールスマン問題のアルゴリズムはありますが、限界ではかなり遅くなる可能性があります（NP困難です）。一方、適切な近似があり、単純なケースは解決できる可能性がありますが、それでも自明ではないアルゴリズムです。

断片化を最大化することの重要性に応じて、単純な方法を試すこともできます。要素を指定して、指定された要素からかなり離れるように次の要素を選択します。次に、次の要素を選択します。これに伴う問題は、あなたの初期の選択があなたを追い詰めることができるということです。したがって、断片化が非常に重要な場合、これは機能しません。

[2,5,1,3,4] // the first three choices force us to not fragment the last two
于 2012-06-06T12:53:33.210 に答える
1

断片化が連続する値の絶対差の合計として定義されていると仮定すると、最大の断片化シーケンスは一意ではありません。逆のシーケンスは常にまったく同じ断片化を持ち、さらに多くのオプションがあります。たとえば、次のすべての順序は次のようになります。この配列の最大値である11の断片化：（3,1,5,2,4）、（3,2,5,1,4）、（2,5,1,4,3）、（2 、4,1,5,3）、（4,1,5,2,3）、（4,2,5,1,3）、（3,5,1,4,2）、（3,4 、1,5,2）。最後の要素と最初の要素の違いも取り入れれば、さらに多くの対称性があります。

特定の最大断片化シーケンス、たとえば「目立つパターンのない」シーケンスを特定しようとする場合、後者の概念を形式化して検索を実行する必要があります。これは、計算の観点からはコストがかかると思われます。目的は、効率的なデコードを可能にするように形式化することができます。各ステップでの断片化のゲインを最大化するために、要素を1つずつ配列に挿入する（貪欲な方法）など、すべての実用的な目的には、優れたヒューリスティックで十分だと思います。

ただし、配列の要素が数値ではなく、ペアごとに距離が定義されている一部のエンティティである場合、user802500が指摘したように、この問題は巡回セールスマン問題と同等になります。

于 2012-06-07T10:50:44.923 に答える