Randomized For...in loop

Question

I was checking Microsoft f# guide on for...in loops and was wondering how could the for in loop be randomized.

For example:

let list1 = [ 1; 5; 100; 450; 788 ]
for i in list1 do
  printfn "%d" i

output:
1
5
100
450
788

If I want to have the elements to be printed in a random order using for in loop, what could I do?

Search "randomize order" here on SO. I think the Fisher–Yates shuffle looks really good. — Bent Tranberg, May 10 '20 at 15:00

score 0 · Accepted Answer · answered May 11 '20 at 06:38

We have established that, essentially, there's only the Fisher–Yates shuffle for randomizing a given collection. Easy to get wrong; here's a C# discussion of Dos and Don'ts.

The freedoms we have left in implementation: we can count upwards or downwards when performing the random swaps, and we may decide to either mutate the array in place, or create a copy of the input data.

// Mutate in place, count downwards
let shuffle arr =
    let rnd = System.Random()
    for i in Array.length arr - 1 .. -1 .. 1 do
        let tmp, j = arr.[i], rnd.Next(0, i)
        arr.[i] <- arr.[j]; arr.[j] <- tmp

let a = [|1; 5; 100; 450; 788|]
shuffle a

// Create a copy, count upwards
let copyShuffle source =
    let arr = Seq.toArray source
    let rnd, len = System.Random(), arr.Length
    for i in 0 .. len - 2 do
        let tmp, j = arr.[i], rnd.Next(i, len)
        arr.[i] <- arr.[j]; arr.[j] <- tmp
    arr

copyShuffle [1; 5; 100; 450; 788]
|> Array.iter (printfn "%i")

Upvote from me, but let's point out that 1) in production code there might be issues with creating System.Random in each call. And 2) System.Random might not be good enough, e.g. for shuffling a deck of cards if money is involved. — Bent Tranberg, May 11 '20 at 08:04
This is a good solution although hardly idiomatic for F#. As pointed by Brent Random should be a parameter of the function. — Koenig Lear, May 14 '20 at 19:31

onemorecupofcoffee · Answer 2 · 2020-05-10T16:16:44.387

-2

Here is an easy way to do it using the random function

let random= new Random()

let randomizeList lst = 
    lst 
    |> List.sortBy (fun (_) -> random.Next(lst.Length * 1000))

let list1 = [ 1; 5; 100; 450; 788 ] 
                |> randomizeList
for i in list1 do
  printfn "%d" i

Please see notes on the Random number generator with regards to randomness - there are better algorithms for producing a more pure random distribution, Dotnet Core Docs -

The chosen numbers are not completely random because a mathematical algorithm is used to select them, but they are sufficiently random for practical purposes.

edited May 10 '20 at 16:16

answered May 10 '20 at 14:55

onemorecupofcoffee

2,237
1
15
21

This answer is extremely flawed, as explained here (see Sorting section) : https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle – Bent Tranberg May 10 '20 at 15:30
I never said this was the best way, but it works. If you use an algorithm such as the suggested Fisher-Yates you would need a mutable list which is not the case in the code posted by the OP – onemorecupofcoffee May 10 '20 at 15:40
No, it can be implemented in various ways, including with lists. The OP asked how to randomize a list, and this simply does not randomize the list in a uniform way. It is described as an "extremely bad method". It doesn't matter whether OP or you like this solution. – Bent Tranberg May 10 '20 at 15:43
@Bent Tranberg I'm looking at how to randomize a list, in particular I'm trying to do it for a list of (x,y) coordinates and it seems that the most suggested way would be to use the List.sortBy function before calling the for in loop. To be more specific I need to do certain actions on every coordinate but the coordinates needs to be picked randomly and not in a spefic order. So the idea is: If I have a list of [xa,ya;xb,yb;xc,yc;xd,yd] I want to perform the actions not in order a,b,c,d but in a random order. Do you think you can help me with that? – Spyromancer May 10 '20 at 16:02
I haven't found an F# implementation of the Fisher-Yates shuffle, but there is a C# implementation here: https://thedeveloperblog.com/fisher-yates-shuffle – Bent Tranberg May 10 '20 at 16:23
Ok, I found more here (search Fisher-Yates on that page): http://rosettacode.org/wiki/Knuth_shuffle#F.23 – Bent Tranberg May 10 '20 at 16:35
There is a similar question with two flawed answers [here](https://stackoverflow.com/questions/31709509/how-to-deal-a-card-using-f), and I made similar comments there. – Bent Tranberg May 10 '20 at 16:39
1

@Bent Tranberg I looked at these, I think I'm close to a solution. thanks – Spyromancer May 10 '20 at 17:35
Yet more information, including details relevant to this answer : https://stackoverflow.com/questions/273313/randomize-a-listt – Bent Tranberg May 10 '20 at 20:33
Upvote from me this is a sufficient good solution. The author did not specify any randomness guarantees. From readability perspective this is very clear how it works. – Koenig Lear May 14 '20 at 19:28

Randomized For...in loop

2 Answers2