Sunday, August 16, 2015

Fisher-Yates Shuffle in Scala

This post describes the Fisher-Yates algorithm to shuffle randomly a sequence of objects.


Overview
The generation of a sequence of randomly ordered elements from an existing sequence is a common problem. How can you be sure if the new sequence of items is actually randomly generated?
The Fisher-Yates shuffle algorithm (a.k.a. Donald Knuth shuffle) produces unbiased permutations with a similar likelihood.
One important benefit of Fisher-Yates is the ability to shuffle the elements of the sequence, in place.

Note:
There are several interpretations of the shuffling algorithm. This post describes the implementation of the most common Fisher-Yates algorithm

Fisher-Yates
Let's look at the implementation of Fisher-Yates
Here is the Fisher-Yates in a nutshell;
Let's consider an array arr of n elements
For each array index k from n-1 to 1
  Select a random value m  between k and 0
  Swap arr[r] and arr[k]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def fisherYates[T](t: Seq[T]): Seq[T] = {

  setSeed(System.currentTimeMillis)
  
  (0 until t.size).foreach (n => {
     val randomIdx = n + nextInt(t.size-n)
     val tmp = t(randomIdx)
     t.update(randomIdx, t(n))
     t(n) = tmp
  })
  t
} 

The Fisher-Yates algorithm executes as an iteration with the following two steps:
  • Select a random item in the remaining sequence< (line 6)/li>
  • Swap the randomly selected item with the current item (lines 8,9)

Fast Fisher-Yates implementation
The performance of the Fisher-Yates algorithm can be improved by implementing the swapping of the randomly selected item with the current time in-place using bit manipulation operators.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def fisherYates2(seq: mutable.Seq[Int]): IndexedSeq[Int] = {
  require(seq.size > 0, "Undefined argument")

  setSeed(System.currentTimeMillis)
  (0 until seq.size).map(i => {
     var randomIdx: Int = i + nextInt(seq.size-i)
     seq(randomIdx) ^= seq(i)
     seq(i) = seq(randomIdx) ^ seq(i) 
     seq(randomIdx) ^= (seq(i))
     seq(i)
  })
}

The following code snippet tests the two implementations of the Fisher-Yates shuffling algorithm.
  val input = Array[Char](
    'a', 't', '4', '&', '9', '2', 'z', 'y', 'r', '8', '*', '?'
  )
  println(fisherYates[Char](input).mkString(","))
  // t,&,*,2,a,r,4,z,?,y,8,9

  println(fisherYates2(Array.tabulate(34)(n => n)).mkString(","))
  // 9,24,11,29,1,31,28,20,6,18,23,0,13,17,22,0,27,
  // 4,16,7,25,14,30,32,5,12,8,19,21,0,0,33,26,0
Note:
Scala standard library provides developers with a shuffling method: Random.shuffle.

Reference

15 comments:

  1. Seq is not mutable.

    def fisherYates[T](t: Buffer[T]): Buffer[T] = {

    r.setSeed(System.currentTimeMillis)

    (0 until t.size).foreach (n => {
    println(n)
    val randomIdx = n + r.nextInt(t.size-n)
    val tmp = t(randomIdx)
    t.update(randomIdx, t(n))
    t(n) = tmp
    })
    t
    }

    ReplyDelete
  2. When finding that correct rhythm, that specific example that drive the fish totally nuts for your bait, you generally need to remember: Slow-Fast-Medium. These are the three velocities you need to alter with so as to get to that rhythm.fishing holiday in thailand

    ReplyDelete

  3. اعالى الخليج تقدم افضل خدمات نقل العفش الدولى المتميزه باسعار متميزة ومنها :

    شركة شحن عفش من الرياض الى دبي
    نقل عفش من الرياض الى الاردن شحن عفش من الرياض الى الاردن

    ReplyDelete
  4. Crypto-currency as a modern form of the digital asset has received a worldwide acclaim for easy and faster financial transactions and its awareness among people have allowed them to take more interest in the field thus opening up new and advanced ways of making payments. Crypto.com Referral Code with the growing demand of this global phenomenon more,new traders and business owners are now willing to invest in this currency platform despite its fluctuating prices however it is quite difficult to choose the best one when the market is full. In the list of crypto-currencies bit-coins is one of the oldest and more popular Crypto.com Referral Code for the last few years. It is basically used for trading goods and services and has become the part of the so-called computerized block-chain system allowing anyone to use it thus increasing the craze among the public, Crypto.com Referral Code.

    Common people who are willing to purchase BTC can use an online wallet system for buying them safely in exchange of cash or credit cards and in a comfortable way from the thousands of BTC foundations around the world and keep them as assets for the future. Due to its popularity, many corporate investors are now accepting them as cross-border payments and the rise is unstoppable. With the advent of the internet and mobile devices,information gathering has become quite easy as a result the BTC financial transactions are accessible and its price is set in accordance with people’s choice and preferences thus leading to a profitable investment with Crypto.com Referral Code. Recent surveys have also proved that instability is good for BTC exchange as if there is instability and political unrest in the country due to which banks suffer then investing in BTC can surely be a better option. Again bit-coin transaction fees are pretty cheaper and a more convenient technology for making contracts thus attracting the crowd. The BTC can also be converted into different fiat currencies and is used for trading of securities, for land titles, document stamping, public rewards and vice versa.

    Another advanced block-chain project is Ethereumor the ETH which has served much more than just a digital form of crypto-currency Crypto.com Referral Code and its popularity in the last few decades have allowed billions of people to hold wallets for them. With the ease of the online world,the ETH have allowed the retailers and business organizations to accept them for trading purposes, therefore, can serve as the future of the financial system.

    ReplyDelete
  5. BUY EMAIL LEADS
    If your company is in the look-out for investors or new business endeavours, business opportunity leads provide you information of those wanting to start a business. They are an email away from being a buyer or your business partner.Time is of the essence in every marketing strategy. Direct mail, for example, purchase email lists takes an extended time from the campaign period to implementation. Not all companies can afford to spend such amount of time to get marketing results. This may be one of the reasons why email marketing became popular. Thanks to modernization and high technology, with your email contact list, you can reach and convey your message to thousands of people with just a few clicks away.

    ReplyDelete
  6. Internet Download Manager 6.38 Build 10 IDM Crack Patch with Serial Crucial down load is a sort of shareware downloadmanager possessed by an American company called Tonec Inc.. IDM Patch Free Download captures any type of download in a extraordinary time limit and completes the download at a very brief time and at a faster speed as compared to any download manager right now. IDM company is based in nyc. This computer program is readily designed for Windows OS just for now.
    Presently IDM Serial Crucial Free has turned into a renowned application with over 20 million clients around the globe. Internet download manager Hack may take downloads from many browsers like Internet Explorer, Microsoft Edge, IDM Crack with Serial Key Google Chrome, Opera, Firefox for practically just about any kind of record of user's choice. It has gained control over down load; nevertheless, it shows its dialog box to an individual.

    ReplyDelete
  7. Dubai company listings has business listings, phone numbers, maps, email addresses and websites for local businesses in Dubai to help you get the job do.

    ReplyDelete
  8. Friendly Finance is South Africa's number 1 choice for finance - providing customers with all the information they need to make better financial decisions. We provide hundreds of comparisons of common consumer finance products, pay day loans such as personal loans, car loans, short-term loans and credit cards. Think of us as a helping hand in selecting consumer finance products.


    ReplyDelete
  9. Testimonial Review of Taskade, Taskade Testimonials the all-in-one collaboration platform for remote teams. Unleash your team productivity with task lists, mindmaps, and video chat.

    ReplyDelete
  10. Recently, the keto diet has become extremely popular for its health benefits such as weight loss and preventing disease. A custom Keto plan for life! Visit: how to start keto diet

    ReplyDelete
  11. Health Experts have proven that regular exercise coupled with a good diet allow you to live longer and healthier. In this busy day and age, not everyone has the time to go to the gym - resulting to a lot of overweight people that desperately need to exercise. A healthy alternative is for you to Buy Home Gym Equipments that you can store in your own home or even at your office. Here are some tips when buying home gym equipment.

    First, know your fitness goals and keep these goals in mind when you are buying home gym equipment. One of the biggest mistakes that people make is buying the biggest or trendiest fitness machine simply because they like how it looks. More often than not, these end up gathering dust in your storage rooms or garage because you never end up using them. It is important to take note of what particular type of physical activity you want or enjoy doing before you buy your exercise machine. If you are looking to loose a few pounds and you enjoy walking or hiking, a treadmill is the best option for you. If you are looking to tone your lower body while burning calories a stationary bike is your obvious choice. Similarly, Special Equipments for Core Strength Exercises, Strength Training Weight Vests, Core Strength & Abdominal Trainers, Home Cardio Training, Strength Training Power Cages, Strength Training Racks & More.

    Second, set aside a budget before Buying Home Gym Equipments. Quality exercise machines do not come cheap. They are constantly exposed to wear and tear when they are used properly. So, pick machines that are built to last and have passed quality certifications to get the most out of your money. If you are operating on a tight budget, think about investing in several weights, We can Provide you High Quality Home Gym Equipments at Very Low Prices for your Complete Uses: Core Strength Exercises, Strength Training Weight Vests, Core Strength & Abdominal Trainers, Home Cardio Training, Strength Training Power Cages, Strength Training Racks & More.

    Its the Right Time to Buy Home Gym Equipments for you at Very Low Prices.

    ReplyDelete
  12. - Como organizar sua Semana com o Taskade - Segunda Feira, primeiro dia.
    - Como organizar sua semana com o Taskade - Terça - Vlog de Produtividade
    - Como organizar sua semana com o Taskade - Quarta
    Como organizar sua semana com o Taskade - Quinta - Vlog Produtividade.
    - Taskade - Sexta, Sábado e Domingo. Como foi e uma grande novidade

    ReplyDelete
  13. We are a clean skincare brand, 100% organic and made with what the earth has given us first. Our product formulations came from listening to our ingredients. From their benefits, scents and results, our products are truly science of the earth. https://en.gravatar.com/firstbaseskncare We wanted to step back from the long list of hard to pronounce scientific gibberish and provide ingredients relatable and understood. We are very proud to be one of the first few on the market to be ECO-Certified under the COSMOS standards, and for us we want to leave the earth better than we found it.

    ReplyDelete
  14. Are Anabolic Steroids and Body Building Supplements Safe to Use?


    Anabolic steroids and lifting weights supplements are a questionable way that numerous competitors and jocks to construct muscle. Frequently alluded to as these steroids, these enhancements are introduced in both regular and engineered structures. Heaps of the debate concerns the engineered structure because of the destructive results that weight lifters can experience the ill effects of. Characteristic anabolic enhancements will in general be less destructive whenever utilized with some restraint. In any case, Sp laboratories Anabolic steroids advance cell development and division, which is the regular standard behind weight training since it causes enormous muscles framed from more modest ones.

    Lifting weights Supplements have been demonized by a standing for an assortment of reasons. At the point when competitors and maltreatment of anabolic steroids muscle heads, they acquire an upper hand over their rivals. Thus, authorities in the game of cricket to weight training thought about anabolic steroids and enhancements contrary to the guidelines. This is apparent in the new outrages identified with baseball whizzes like Barry Bonds and Mark McGwire. During the 1980s, the World Wrestling Federation additionally experienced a major embarrassment that prompted the utilization of anabolic steroids and enhancements in the news. These and different outrages have added to the helpless standing of these questionable anabolic enhancements.

    Training on the impacts of anabolic steroids and enhancements is important to help direct individuals from them. Sadly, large numbers of the competitors in secondary school have gone to anabolic enhancements to help them acquire an upper hand against their rivals. With the constructive outcomes that are depicted by proficient competitors, more youthful clients are regularly unconscious of the ramifications as long as possible. Numerous anabolic steroids supplement clients experience the ill effects of hypertension, which can prompt a lot of genuine ramifications and can't be fixed on the body of the client.

    Despite the fact that steroids identical to a lot of debate, it isn't liberated from results positive. In the event that you need to assemble muscle quick, anabolic steroids and enhancements is one approach to do as such. They were additionally utilized in an assortment of clinical medicines until it was restricted in 1988. Pediatricians utilized anabolic to invigorate development in kids with hindered development chemical. Specialists likewise have utilized steroids to help malignancy and AIDS patients increment their hunger and fabricate bulk. Up to this point, specialists additionally used to prompt pubescence in young men. Presently, clinical medicines use testosterone for this reason and to assist competitors with recuperating wounds.

    Enhancements of manufactured steroids are dubious on the grounds that they give expanded strength and bulk, yet at extraordinary expense to the wellbeing of the client. The normal way, in any case, might be less hurtful. Regardless, even common anabolic maltreatment can be inconvenient to their wellbeing and bodies. By and large, can be the master or mentor to exhort you and assist you with finding the most valuable type of lifting weights material to assist you with accomplishing the best outcomes.

    ReplyDelete
  15. Buy Modafinil Online – Buying pills like Modafinil is not easy. Are you trying to purchase modafinil online? If your answer is Yes, then you are in the right place. In this buyer’s guide, we are going to cover everything you need to know about the most popular nootropic in the world.

    ReplyDelete