Math＆php：以特殊方式快速排列數組[1..N]

Question

$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％不同。

我有一個奇怪的任務，但它有一個實用的區域使用。我想從圖像中提取隨機線條，它們應該儘可能不同。當然，數字圖像（照片等）上的相鄰線條看起來非常相似。

我說得對嗎？

Answer 1

我知道提供代碼並不是一個好主意，但我對這個問題很感興趣。這是我會怎麼做：

$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 
) 

唯一的缺點是，由於它隨機獲得行，有機會接近尾聲的值可能不在規定的範圍之外。通過我的測試，使用上述$d = 0.25和1000個值發生的這種情況約爲4％。解決這個問題的一種方法是將這些值重新插入隨機位置，而不是象我所做的那樣追加它們。

另外請注意，這種方法不是那麼高效。它必須遍歷數組count($arr)^2次。因此，對於1000個值，您正在查看1,000,000次迭代。幸運的是，數組逐漸變小。