Математика и php: БЫСТРАЯ сортировка массива [1..N] особым способом

Question

Математика и php: БЫСТРАЯ сортировка массива [1..N] особым способом

$array = array(1, 2, 3, 4, 5, ..., N);

Также есть число D = 10%. Каков самый быстрый способ сортировки массива таким образом, чтобы:

$sorted_array = {a[i]}

Содержит в точности элементы $array в смешанном порядке, но также:

abs(a[i + 1] - a[i]) >= N * 10%

Для любого [i] и выглядеть как можно более рандомизированным.

Например,

// assume D = 25%
$array = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

// so the difference between any neighbors is >= 4 = 10 * 25%.
$sorted_array = array(4, 8, 3, 7, 1, 5, 9, 2, 6, 10);

Конечно, если D большой, невозможно отсортировать массив, который я хочу. Мне не нужен 100 % идеальный результат, но я хочу, чтобы цифры выглядели "рандомизированными", и большинство из них были отличается, по крайней мере, на 10%.

У меня странная задача, но у нее есть практическая область для использования. Я хочу извлечь рандомизированные строки из изображения, и они должны быть как можно более разными. Конечно, соседние линии на цифровых изображениях (фотографиях и т.д.) выглядят очень похожими.

Правильно ли я это объяснил?

4

php arrays sorting optimization math

Author: Haradzieniec, 2013-08-05

Source

1 answers

score 2 · Accepted Answer

Я знаю, что не очень хорошая идея просто предоставлять код, но меня заинтриговал этот вопрос. Вот как бы я это сделал:

$d = 0.3;
$random = array();

// Populate the original array
for ($n=1; $n <= 10; $n++) {
    $arr[] = $n;
}

$count = count($arr);

// Loop through array
foreach (array_keys($arr) as $key) {
    if (!isset($prev_key)) {
        $prev_key = array_rand($arr);
    }
    $possibles = array(); // This stores the possible values
    echo "Trying: $prev_key";
    echo ":\n";

    // Loop through the array again and populate $possibles with all possible
    // values based on the previous values
    foreach (array_keys($arr) as $n) {
        if ($arr[$n] < $prev_key - $count * $d || $arr[$n] > $prev_key + $count * $d) {
            $possibles[] = $n;
            echo $arr[$n]." is valid\n";
        }
        else {
            echo $arr[$n];
            echo " outside range\n";
        }
    }

    // If there is nothing outside that range, just return the remaining values
    if (count($possibles) == 0) {
        $possibles = array_keys($arr);
        echo "Nothing within range so just returning whole array\n";
    }
    echo "\n";

    // Choose random value from the possible values array
    $rand_key = $possibles[array_rand($possibles)];

    $random[] = $arr[$rand_key];
    $prev_key = $arr[$rand_key];

    // Unset this value from the original array since we can only use the
    // values once
    unset($arr[$rand_key]);
}

print_r($random);

Это приведет к следующему результату:

Trying: 8:
1 is valid
2 is valid
3 is valid
4 is valid
5 outside range
6 outside range
7 outside range
8 outside range
9 outside range
10 outside range

Trying: 2:
1 outside range
3 outside range
4 outside range
5 outside range
6 is valid
7 is valid
8 is valid
9 is valid
10 is valid

Trying: 9:
1 is valid
3 is valid
4 is valid
5 is valid
6 outside range
7 outside range
8 outside range
10 outside range

Trying: 5:
1 is valid
3 outside range
4 outside range
6 outside range
7 outside range
8 outside range
10 is valid

Trying: 10:
1 is valid
3 is valid
4 is valid
6 is valid
7 outside range
8 outside range

Trying: 4:
1 outside range
3 outside range
6 outside range
7 outside range
8 is valid

Trying: 8:
1 is valid
3 is valid
6 outside range
7 outside range

Trying: 3:
1 outside range
6 outside range
7 is valid

Trying: 7:
1 is valid
6 outside range

Trying: 1:
6 is valid

Array
(
    [0] => 2
    [1] => 9
    [2] => 5
    [3] => 10
    [4] => 4
    [5] => 8
    [6] => 3
    [7] => 7
    [8] => 1
    [9] => 6
)

Единственным недостатком является то, что, поскольку он случайным образом получает строки, есть вероятность, что значения ближе к концу могут не выходить за пределы определенного диапазона. По моим тестам, это происходит примерно с 4 %, используя приведенные выше значения $d = 0.25 и 1000. Один из способов обойти это - просто вставить эти значения обратно в случайные места вместо того, чтобы добавлять их, как я это сделал.

Также обратите внимание, что этот метод не настолько эффективен. Он должен пройти через массив count($arr) ^ 2 несколько раз. Таким образом, для 1000 значений вы смотрите на 1 000 000 итераций. К счастью, массив постепенно уменьшается.