天道酬勤,学无止境

Fischer Yates shuffle in coffee-script

Assuming that Math.random() produces evenly distributed random numbers between 0 and 1, is this a correct implementation of the Fischer Yates shuffle? I am looking for a very random, even distribution, where the number of shuffled elements in an input array (arr) can be specified (as required).

shuffle = (arr, required)->
  rnd = (int) ->
    r = Math.random() * int
    Math.round r

  len = arr.length-1

  for i in [len..1]
    random = rnd(i)
    temp = arr[random]
    arr[random] = arr[i]
    arr[i] = temp
    break if i < len - (required - 2)

  return arr

评论

A couple things:

  • Rather than Math.round(), try Math.floor(); in your implementation Math.round() gives the first element (at index 0) and the last element less of a chance than all the other elements (.5/len vs. 1/len). Note that on the first iteration, you input arr.length - 1 for arr.length elements.
  • If you're going to have a required variable, you might as well make it optional, in that it defaults to the length of the array: shuffle = (arr, required=arr.length)
  • You return the entire array even though you only shuffled the last elements. Consider instead returning arr[arr.length - required ..]
  • What if required isn't in the range [0,arr.length]?

Putting it all together (and adding some flair):

    shuffle = (arr, required=arr.length) ->
      randInt = (n) -> Math.floor n * Math.random()
      required = arr.length if required > arr.length
      return arr[randInt(arr.length)] if required <= 1

      for i in [arr.length - 1 .. arr.length - required]
        index = randInt(i+1)
        # Exchange the last unshuffled element with the 
        # selected element; reduces algorithm to O(n) time
        [arr[index], arr[i]] = [arr[i], arr[index]]

      # returns only the slice that we shuffled
      arr[arr.length - required ..]

    # Let's test how evenly distributed it really is
    counter = [0,0,0,0,0,0]
    permutations = ["1,2,3","1,3,2","2,1,3","2,3,1","3,2,1","3,1,2"]
    for i in [1..12000]
      x = shuffle([1,2,3])
      counter[permutations.indexOf("#{x}")] += 1

    alert counter

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐
  • 为什么在 Sort 中使用 Random 会导致 [Unable to sort IComparer.Compare 错误](Why does using Random in Sort causing [Unable to sort IComparer.Compare error])
    问题 我尝试使用任一代码改组字节列表(列表): myList.Sort((a, b) => this._Rnd.Next(-1, 1)); 或者 myList.Sort(delegate(byte b1, byte b2) { return this._Rnd.Next(-1, 1); }); 他们抛出了以下错误: 无法排序,因为 IComparer.Compare() 方法返回不一致的结果。 要么一个值不等于它自己,要么一个值与另一个值重复比较会产生不同的结果。 x:“{0}”,x 的类型:“{1}”,IComparer:“{2}”。 使用随机而不是字节的比较函数有什么问题? 我尝试改用 LINQ 函数并且它有效。 var myNewList = myList.OrderBy(s => Guid.NewGuid()); var myNewList = myList.OrderBy(s => this._Rnd.NextDouble()); 我确实读到这些方法比仅给出 O(n) 运行时间的 Fisher-Yates shuffle 慢。 但只是想知道如何使用 Sort 函数和 random。 回答1 因为正如错误所说, Random 不一致。 您必须有一个在给定相同参数时始终返回相同结果的比较器。 否则排序将不一致。 Knuth 有一个随机排序算法,它的工作方式类似于插入排序
  • 如何随机化(随机播放)JavaScript数组?(How to randomize (shuffle) a JavaScript array?)
    问题 我有一个像这样的数组: var arr1 = ["a", "b", "c", "d"]; 如何将其随机/随机播放? 回答1 实际无偏混洗算法是Fisher-Yates(又名Knuth)混洗。 参见https://github.com/coolaj86/knuth-shuffle 您可以在此处看到出色的可视化效果(以及与此相关的原始文章) function shuffle(array) { var currentIndex = array.length, temporaryValue, randomIndex; // While there remain elements to shuffle... while (0 !== currentIndex) { // Pick a remaining element... randomIndex = Math.floor(Math.random() * currentIndex); currentIndex -= 1; // And swap it with the current element. temporaryValue = array[currentIndex]; array[currentIndex] = array[randomIndex]; array[randomIndex] = temporaryValue; }
  • AngularJS 1.2中的random orderBy返回'infdig'错误(random orderBy in AngularJS 1.2 returns 'infdig' errors)
    问题 在此问题中使用random orderBy排序技术在AngularJS 1.1中工作正常。 var myApp = angular.module('myApp',[]); function MyCtrl($scope) { $scope.list = ['a', 'b', 'c', 'd', 'e', 'f', 'g']; $scope.random = function() { return 0.5 - Math.random(); } } 不过,在1.2版中,它将infdig错误放入控制台,并花费了更长的时间返回排序后的结果:http://jsfiddle.net/mblase75/jVs27/ 控制台中的错误如下所示: Error: [$rootScope:infdig] 10 $digest() iterations reached. Aborting! Watchers fired in the last 5 iterations: [["fn: $watchCollectionWatch; newVal: 42; oldVal: 36"],["fn: $watchCollectionWatch; newVal: 47; oldVal: 42"],["fn: $watchCollectionWatch; newVal: 54; oldVal: 47"],["fn:
  • 在C#中使用0-9之间的uniqe随机数填充数组(filling a array with uniqe random numbers between 0-9 in c#)
    问题 我想在C#中使用0-9之间的唯一随机数填充数组,我尝试使用此函数: IEnumerable<int> UniqueRandom(int minInclusive, int maxInclusive) { List<int> candidates = new List<int>(); for (int i = minInclusive; i <= maxInclusive; i++) { candidates.Add(i); } Random rnd = new Random(); while (candidates.Count > 1) { int index = rnd.Next(candidates.Count); yield return candidates[index]; candidates.RemoveAt(index); } } 我这样使用它: for (int i = 0; i < 3; i++) { page[i] = UniqueRandom(0, 9); } 但是我得到了错误: Cannot implicitly convert type 'System.Collections.Generic.IEnumerable<int>' to 'int' 我还添加了以下名称空间: using System.Collections.Generic
  • C中的Fisher Yates改组算法(Fisher Yates shuffling algorithm in C)
    问题 我被要求分配使用函数在要从文件中获取的数组上使用 FisherYates shuffle(我设法做到了)。 int FisherYates(int *player, int n) { //implementation of Fisher int i, j, tmp; // create local variables to hold values for shuffle for (i = n - 1; i > 0; i--) { // for loop to shuffle j = rand(); //randomise j for shuffle with Fisher Yates tmp = player[j]; player[j] = player[i]; player[i] = tmp; } return player; } 它基本上只需要打乱玩家列表并将输出返回给我,这样我就可以在 main() 中将其打印出来。 如果有人能告诉我如何修改代码以使其工作,我将非常感激,因为在这个版本中,我在编译时收到错误: invalid conversion from 'int*' to 'int' [-fpermissive] 回答1 您已经在player获得了结果,因此返回void应该可以工作。 Fisher-Yates 的参考 void FisherYates(int
  • 使用随机数生成器对整数进行随机排列(Random permutation of integers using a random number generator)
    问题 这是我的作业: Random r = new Random(); public int get100RandomNumber() { return 1+r.nextInt(100); } 您将获得一个名为getrand100()的预定义函数(上面),该函数返回一个整数,该整数是1到100之间的一个随机数。 您可以根据需要多次调用此函数,但是请注意,此函数会占用大量资源。 您不能使用任何其他随机生成器。 您不能更改getrand100()的定义。 输出:以随机顺序打印数字1-20。 (不是20个随机数) 我尝试过的.. public class MyClass { static Random r = new Random(); static HashSet<Integer>; public static void main(String args[]) { myMethod(); System.out.println(s); } public static void myMethod() { boolean b = false; s = new HashSet<Integer>(); int i = getRand100(); if (i >= 20) i = i % 20; int j = 0; int k, l; while (s.size() <= 20) {
  • Fisher-Yates shuffle 的这个 C 实现是否正确?(Is this C implementation of Fisher-Yates shuffle correct?)
    问题 这是我想在甲板洗牌例程中使用的 Fisher-Yates 的 C 实现。 我这样做是否正确(n = 数组长度)? 注意:do-while 循环尝试纠正模偏差(请参阅此处)。 这会增加该过程的开销,并且如果您不在乎低位偏差,则可以消除该开销。 void shuffle(int *array, int n) { int i, j, tmp, upper_bound; srand(time(NULL)); for (i = n - 1; i > 0; i--) { upper_bound = RAND_MAX - ((RAND_MAX % (i + 1)) + 1); do { j = rand() % (i + 1); } while (j > upper_bound); tmp = array[j]; array[j] = array[i]; array[i] = tmp; } } 回答1 首先,您应该提取用于生成在0 (含)和n (不含)之间均匀分布的随机数的代码到一个单独的函数。 这是一项很好的工作,您还将需要在其他地方进行工作。 其次,我不会在shuffle函数内部调用srand ,而是依赖于调用者初始化随机数生成器。 这样你可以在一秒钟内多次洗牌。 第三,在除以i + 1之前,应先对j > upper_bound进行测试。 这是不可能的, i将永远不会接近RAND
  • 费雪·耶茨(Fisher Yates)洗牌名单(Fisher Yates Shuffle on a Cards List)
    问题 我正在尝试在卡片列表上进行费舍尔·耶茨(Fisher Yates)洗牌。 我在论坛上进行了搜索,Fisher Yates的唯一实现是使用如下所示的常规int数组 for (int i = length - 1; i > 0; i--) { int j = random.Next(i + 1); int temp = array[i]; array[i] = array[j]; array[j] = temp; } 这很合理,我的麻烦是我没有真正看到如何将这种逻辑转换为我拥有的事物的方式,在实现此目标方面的任何帮助将不胜感激。 相关代码如下: public struct Card : IComparable<Card> { public Rank Rank { get; private set; } public Suit Suit { get; private set; } public Card(Rank rank, Suit suit) : this() { Rank = rank; Suit = suit; } public override string ToString() { return string.Format("{0:x} {1}", (char) Suit, Rank); } } public enum Suit { Spades = 9824
  • Fisher-Yates 在单个字符串上与使用等长排列进行混洗?(Fisher-Yates shuffle on a single string vs. using an equal length permutation?)
    问题 现在我正在开发一套文字游戏,作为自学的一种手段(并重新创建一些我最喜欢的文字游戏!)在一位“实际”学习过的编程朋友的帮助下,我们在其中一个实现了一个很好的排列方法我的课程。 它正在查找 3 个字母及以上的所有排列,并将它们与我拥有的字符串列表进行比较,其中包含基本上是拼字游戏锦标赛单词列表的内容。 这是背景,这是我当前的问题:我现在拥有所有排列并将它们与现有单词进行比较,并创建了一个新列表,其中包含给定字符串中所有可能的单词组合。 但是,当我将此字符串呈现给用户时,我需要对其进行加扰。 我发现了 Fisher-Yates shuffle 的一些 C# 实现,但我未能将它们调整为接受单个字符串(编辑:Fisher-Yates 问题已通过 char[] 数组解决)。 然后我有了一个小技巧——为什么不使用长度相同但 != 原始单词的排列之一。 不幸的是,每次我的条件语句都会向后返回单词。 最终用户并不难弄清楚:) 这是我的加扰代码: // permWords is a Dictionary<int, List<string>> String strScrambled= ""; foreach (List<string> listWords in permWords.Values) { foreach (string word in listWords) { if (word
  • Fisher Yates Shuffle on a Cards List
    I'm trying to do the Fisher Yates shuffle on a list of Cards. I've scoured forums and the only implementation of Fisher Yates is with normal int arrays like below for (int i = length - 1; i > 0; i--) { int j = random.Next(i + 1); int temp = array[i]; array[i] = array[j]; array[j] = temp; } Which makes sense just fine, my trouble is I don't really see how to convert that logic to the way I have things, any help in accomplishing this would be greatly appreciated. Relevant code below: public struct Card : IComparable<Card> { public Rank Rank { get; private set; } public Suit Suit { get; private
  • Fisher Yates shuffling algorithm in C
    I have been asked for an assignment to use FisherYates shuffle on an array to be taken in from a file (that, I managed to do) using functions. int FisherYates(int *player, int n) { //implementation of Fisher int i, j, tmp; // create local variables to hold values for shuffle for (i = n - 1; i > 0; i--) { // for loop to shuffle j = rand(); //randomise j for shuffle with Fisher Yates tmp = player[j]; player[j] = player[i]; player[i] = tmp; } return player; } It basically just needs to shuffle the list of players and return me the output so I can print it out in main(). I would very much
  • Is this C implementation of Fisher-Yates shuffle correct?
    Here's a C implementation of Fisher-Yates that I want to use in a deck-shuffling routine. Am I doing this correctly (n = length of array)? Note: The do-while loop attempts to correct for the modulo bias (see here). It adds a bit of overhead to the procedure and could be eliminated if you don't care about the low-bit bias. void shuffle(int *array, int n) { int i, j, tmp, upper_bound; srand(time(NULL)); for (i = n - 1; i > 0; i--) { upper_bound = RAND_MAX - ((RAND_MAX % (i + 1)) + 1); do { j = rand() % (i + 1); } while (j > upper_bound); tmp = array[j]; array[j] = array[i]; array[i] = tmp; } }
  • 如何在Perl中以随机顺序在STDIN中打印行?(How can I print the lines in STDIN in random order in Perl?)
    问题 我想做sort(1)的反函数:在Perl中将stdin的每一行随机化为stdout 。 回答1 我敢打赌,真正的Perl黑客会撕碎这一点,但是尽管如此,它还是可以做到的。 use strict; use warnings; use List::Util 'shuffle'; my @lines = (); my $bufsize = 512; while(<STDIN>) { push @lines, $_; if (@lines == $bufsize) { print shuffle(@lines); undef @lines; } } print shuffle(@lines); 此解决方案与其他解决方案之间的区别: 不会消耗所有输入,然后将其随机化(内存生猪),但是将随机化每条$ bufsize的行(与其他选择相比,它并不是真正随机且慢的狗)。 使用返回新列表的模块,而不是就地编辑Fisher-Yates实现的模块。 它们是可互换的(除非您必须将打印与随机播放分开)。 有关更多信息,请在您的shell上键入perldoc -q rand。 回答2 这个perl片段可以解决这个问题: #! /usr/bin/perl # randomize cat # fisher_yates_shuffle code copied from Perl Cookbook # (By
  • Fisher-Yates shuffle on a single string vs. using an equal length permutation?
    Right now I am working on a suite of word games as a means of teaching myself (and recreating some of my favorite word games!) With the help of an 'actual' studied programming friend, we have implemented a nice permutation method in one of my classes. It is finding all permutations from 3 letters and up and comparing them to Lists of strings I have containing what is essentially the Scrabble tournament word list. That's the background, here is my current issue: I now have all of the permutations and have compared them to existing words and created a new List with all possible words
  • 如何随机打乱向量中的元素(How to shuffle elements in a vector randomly)
    问题 我正在尝试执行一项需要发生以下情况的作业: 请求所需的元素数 n。 用元素 0, 1, 2, ..., n – 1 填充一个向量并将其显示到控制台。 随机排列元素并将新排列显示到控制台。 我有输入向量,但我不知道如何打乱向量。 注意:我不能使用 random_shuffle 函数或任何函数(除了 .swap() 或这里的索引)所以不要说要这样做。 到目前为止我所拥有的是 #include <iostream> #include <vector> #include <cstdlib> #include <ctime> #include <algorithm> using namespace std; int main() { srand(time(NULL)); vector<int> elements; int sizeOfVector; // size of the vector cout << "Please enter the size of the vector: " << endl; cin >> sizeOfVector; cout << "This is your vector:" << endl; // Output each element in the vector for (int i = 0; i < sizeOfVector; ++i) {
  • 验证 Knuth shuffle 算法尽可能无偏(Verify Knuth shuffle algorithm is as unbiased as possible)
    问题 我正在为我正在处理的 C++ 项目实施 Knuth shuffle。 我试图从我的 shuffle 中获得最公正的结果(而且我不是(伪)随机数生成方面的专家)。 我只是想确保这是最无偏见的 shuffle 实现。 draw_t是一个字节类型( typedef 'd to unsigned char )。 items是列表中的项目数。 我在下面包含了random::get( draw_t max )的代码。 for( draw_t pull_index = (items - 1); pull_index > 1; pull_index-- ) { draw_t push_index = random::get( pull_index ); draw_t push_item = this->_list[push_index]; draw_t pull_item = this->_list[pull_index]; this->_list[push_index] = pull_item; this->_list[pull_index] = push_item; } 我使用的随机函数已被修改以消除模偏差。 RAND_MAX被分配给random::_internal_max 。 draw_t random::get( draw_t max ) { if( random::_is
  • 如何在JavaScript中对字符串中的字符进行随机播放?(How do I shuffle the characters in a string in JavaScript?)
    问题 特别是,我要确保避免在Microsoft的Browser Choice随机代码中犯的错误。 也就是说,我要确保每个字母在每个可能位置出现的可能性均等。 例如,给定“ ABCDEFG”,则返回类似“ GEFBDCA”的内容。 回答1 我修改了Wikipedia上的Fisher-Yates Shuffle条目中的示例以对字符串进行混洗: String.prototype.shuffle = function () { var a = this.split(""), n = a.length; for(var i = n - 1; i > 0; i--) { var j = Math.floor(Math.random() * (i + 1)); var tmp = a[i]; a[i] = a[j]; a[j] = tmp; } return a.join(""); } console.log("the quick brown fox jumps over the lazy dog".shuffle()); //-> "veolrm hth ke opynug tusbxq ocrad ofeizwj" console.log("the quick brown fox jumps over the lazy dog".shuffle()); //-> "o dt hutpe u
  • 改组NSMutableArray的最佳方法是什么?(What's the Best Way to Shuffle an NSMutableArray?)
    问题 如果您有NSMutableArray ,如何随机地随机排列元素? (对此我有自己的答案,发布在下面,但是我是Cocoa的新手,我想知道是否有更好的方法。) 更新:@Mukesh指出,从iOS 10+和m​​acOS 10.12+开始,有一个-[NSMutableArray shuffledArray]方法可用于随机播放。 有关详细信息,请参见https://developer.apple.com/documentation/foundation/nsarray/1640855-shuffledarray?language=objc。 (但是请注意,这将创建一个新的数组,而不是将元素改组到适当的位置。) 回答1 您不需要swapObjectAtIndex方法。 exchangeObjectAtIndex:withObjectAtIndex:已经存在。 回答2 我通过在NSMutableArray中添加一个类别来解决此问题。 编辑:删除不必要的方法,感谢拉德(Ladd)的回答。 编辑:由于格雷戈里·戈尔佐夫(Gregory Goltsov arc4random_uniform(nElements)回答以及miho和blahdiblah的评论,将(arc4random() % nElements)更改为arc4random_uniform(nElements) 编辑:循环改进
  • 随机化StringList(Randomize StringList)
    问题 如何像此在线工具一样,如何在StringList中对字符串进行随机化。 如果有人熟悉它,请检查以下内容:http://textmechanic.co/Randomize-List.html 回答1 进行随机播放的一种常见算法是Fisher-Yates随机播放。 这产生均匀分布的排列。 要在Delphi TStrings对象上实现,可以使用以下命令: procedure Shuffle(Strings: TStrings); var i: Integer; begin for i := Strings.Count-1 downto 1 do Strings.Exchange(i, Random(i+1)); end; 现在,尽管从理论上讲这将生成均匀分布的排列,但实际性能在很大程度上取决于随机数生成器的质量。 这在Knuth的计算机程序设计艺术,第2卷,第3.4.2节,算法P中进行了讨论。 进一步阅读: Fisher-Yates洗牌(Wikipedia) 杰夫·阿特伍德(Jeff Attwood)的两篇关于改组的博客文章:改组和Naïveté的危险 Fisher-Yates改组背后的直觉(Eli Bendersky) 计算机编程艺术,Donald Knuth,第2卷,第3.4.2节改组(维基百科) 回答2 只需遍历字符串列表,并为每个项目分配一个不同的随机位置: for i
  • 使用JavaScript Array.sort()方法进行改组是否正确?(Is it correct to use JavaScript Array.sort() method for shuffling?)
    问题 我正在帮助某人使用他的JavaScript代码,而我的眼睛被一段看起来像这样的部分所吸引: function randOrd(){ return (Math.round(Math.random())-0.5); } coords.sort(randOrd); alert(coords); 我的第一个想法是:嘿,这可能行不通! 但是后来我做了一些实验,发现它确实至少提供了很好的随机结果。 然后,我进行了一些网络搜索,几乎在顶部找到了一篇文章,该文章是最不经意地被复制的。 看起来像一个相当受人尊敬的网站和作者。 但是我的直觉告诉我,这一定是错误的。 特别是由于ECMA标准未指定排序算法。 我认为不同的排序算法将导致不同的不均匀混洗。 一些排序算法甚至可能会无限循环... 但是你觉得呢? 还有另一个问题……我现在将如何去衡量这种混洗技术的结果有多随机? 更新:我进行了一些测量,并将结果发布在下面作为答案之一。 回答1 这从来不是我最喜欢的改组方式,部分原因是您所说的是特定于实现的。 尤其是,我似乎还记得从Java或.NET(不确定哪个)进行标准库排序通常可以检测到某些元素之间的比较结果是否不一致(例如,您首先声明A < B和B < C ,但是C < A )。 最后,它会以比您真正需要的更复杂的(就执行时间而言)洗牌结束。 我更喜欢shuffle算法,该算法可以有效地将集合划分为“