$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% 的差异。
我有一个奇怪的任务,但它有一个实用的领域。我想从图像中提取随机线条,它们应该尽可能不同。当然,数字图像(照片等)上的相邻线条看起来非常相似。
我解释的对吗?
最佳答案
我知道仅仅提供代码不是一个好主意,但我对这个问题很感兴趣。以下是我的做法:
$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 次迭代。幸运的是,阵列逐渐变小。
关于php - Math & php : FAST sort of an array [1. .N] 以一种特殊的方式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18066296/