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

您可以将列表分成两个（或更多）集合，将它们打乱然后按顺序混合它们？

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

我认为这听起来像是一个旅行推销员类型的问题，“距离”是两个选定条目之间的差异，除了你的目标是最大化总距离而不是最小化它。

我实际上对这个话题并不了解很多，但这是我认为我知道的：

旅行商问题有一些算法，但在极限范围内它们可能非常慢（它们是NP-hard）。另一方面，有很好的近似，简单的情况可能是可以解决的，尽管它仍然是一个不平凡的算法。

根据最大碎片的重要性，您还可以尝试一种简单的方法：给定一个元素，选择下一个元素，使其与给定元素相距甚远。然后选择下一个元素，依此类推。这样做的问题是，您的早期选择会使您陷入困境。因此，如果碎片对您来说非常重要，这将不起作用。

[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)。如果还包含最后一个元素和第一个元素之间的差异，则会有更多的对称性。

如果要确定一个特定的最大碎片序列，例如“没有明显模式”的序列，则必须将后一种概念形式化并执行搜索，我怀疑从计算的角度来看，这将是昂贵的，除非目标可以被形式化以允许有效解码。我怀疑出于所有实际目的，一个好的启发式方法就足够了，例如将元素一个一个地插入到数组中（贪婪的方式），以便在每个步骤中最大化碎片的增益。

但是，如果数组的元素不是数字，而是一些实体，每对都有定义的距离，那么问题确实等同于旅行商问题，正如 user802500 指出的那样。

于 2012-06-07T10:50:44.923 回答