有一个这样的数组:
var arr1 = ["a", "b", "c", "d"];
我怎么能随机改变它的顺序?
最好以通用的方式回答以作为任何语言的实现示例
【改变数组内数组数据的顺序】
*这个问题最初是关于 js 和 jQuery 的。
PS:这个问题在英文版中已经存在了,但是我觉得很有趣,我再次提出它并为讲西班牙语的用户改编它。我会留一些时间让人们提供答案。如果没有,我将翻译最佳答案并添加来自房子的贡献。
有一个这样的数组:
var arr1 = ["a", "b", "c", "d"];
我怎么能随机改变它的顺序?
最好以通用的方式回答以作为任何语言的实现示例
【改变数组内数组数据的顺序】
*这个问题最初是关于 js 和 jQuery 的。
PS:这个问题在英文版中已经存在了,但是我觉得很有趣,我再次提出它并为讲西班牙语的用户改编它。我会留一些时间让人们提供答案。如果没有,我将翻译最佳答案并添加来自房子的贡献。
警告
在javascript中有一种非常简单的方法。
解释:
该函数
Math.random()
返回一个介于 0 和 0.9999 之间的随机数...,我们通过减去 0.5 实现的是它生成负数和正数,以便函数sort()
随机重新排序数组,将一个元素放在另一个元素的前面。由于这个问题可能会因语言而有不同的答案,因此我们将讨论算法,而不考虑语言(甚至可以说它可以在数据库中完成)。
我最喜欢混合向量(或使其所有数据乱序)的方法之一,它不是完全高性能但它有效,是生成一个新的混合向量,并将它们组合起来。
假设我们有一个数字向量 (1,2,3...100),我们想要混合它。每个数字在向量中都有一个索引(在这种情况下,索引将等于相同的数字)。我们按以下方式使用具有位置的数组
我们要做的是,对于这个矩阵的每一行,生成一个随机数,该数列在 order 列中。随机数生成必须足够大以覆盖要混合的案例数量。
这样,我们可能会得到这样的东西:
在此之后,我们按顺序列对该矩阵进行排序:
请注意,如果两个位置具有相同的顺序,那没关系,因为它们仍然会混合。显然,您可以使用一个随机函数来返回几乎没有冲突的情况。
一旦这个过程完成,根据原始向量的预期用途,可以使用矩阵给出的新顺序重新生成位置,或者可以简单地按照新矩阵给出的顺序删除必要的项目。
我在 Android 中使用此代码来排列数组而不重复。
提供的其他解决方案取决于对
sort()
. 如果您正在使用的语言实现了该功能,那么它可能是一个很好的解决方案。但是,如果您使用没有 的语言工作,则sort()
必须自己实现一个,这会使问题不必要地复杂化。此外,该解决方案的复杂度将大于 O(N),因为首先需要一个复杂度为 O(N) 的循环来生成随机数,然后再需要另一个复杂度为 O(N log(N)) 的循环来对它们进行排序(假设QuickSort 排序算法,它是最优化的算法之一,也是在大多数语言中实现的算法)-我想出了另一个简单的算法,它不依赖于
sort()
并且具有 O(N) 复杂度,如下所示:该算法从以下思想开始。想象一下,你有一副真正的纸牌。混合它们的一个非常简单的方法是从牌堆中随机取出卡片并将它们放在桌子上,一张放在另一张上面。一旦它们都放在桌子上,它们就会混合在一起。随着这个循环的每一次“迭代”,你手中的牌就会减少。
对此的字面模拟是从列表中取出一个随机项目并将其移动到另一个数组(放置卡片的“表”)。然后,为了完成已抽牌的模拟,原始数组必须“收缩”,这将通过将原始数组的所有元素从所选元素移回一个位置来实现。
我建议的算法保存了移位,而不是将列表中的最后一个数据移动到间隙中。每次选择一个元素时,这都会更改原始列表,但它是否相对于其初始状态无序并不重要。我们正在洗牌!我们还通过使用列表本身作为“表格”将第二个列表保存在其最终位置。因此,通过使用单个列表,它在时间和内存方面都很有效。
一个实现(例如在 Python 中)将是:
例如产生:
版
在做了一些研究之后,我发现(显然)其他人之前已经想到了这个算法 :-) 具体来说,它是由 Donald Knuth 在他的《计算机编程艺术》一书中推广的Fisher-Yates 算法。它似乎是一种广泛使用的算法,因为它在空间和执行时间上是最优的。