0

I was reading about "Naive" shuffling algorithm and the ideal one "Fisher-Yates" Algorithm. I got the difference and also got to know that Naive algorithm favours some permutations while it disfavors some.

Here is a blog that explains the difference about the them and everything that I said.

My question is about the naive shuffling algorithm. I would like to know which permutations is/are most likely and which is/are least likely to occur? This was the only thing not discussed in the blog.

For example :

If we shuffle 4 cards numbered 1 through 4 using this naive algorithm

2, 1, 4, 3 is most likely to occur of all 4^4 =(256) permutations that will be generated by naive algorithm. Likewise 4, 3, 2, 1 is least likely to occur.

For reference here is the "naive" shuffling algorithm:

arr := [1, 2, ..., N]
for i in 1..N do 
    j := rand(1, N)   
   swap(arr[i], arr[j])

EDIT : Already checked this site for similar questions but got no answer that talks about probability of most and least likely permutations. They are all simply explaining the biased results of naive algorithm.

coder3101
  • 3,920
  • 3
  • 24
  • 28
  • There aren't 4^4 combinations, there are 4! – Mitch Sep 12 '18 at 21:33
  • Actually there is 4^4 because then only you can have non distinct permutations. That is total distinct number of permutations. However as I mentioned the naive one repeats some and generate 4^4 repeating permutations. – coder3101 Sep 12 '18 at 21:35
  • Where did you get the idea that the naive shuffle doesn't shuffle? Perhaps you should try *writing some code* to test your hypothesis. This is for a *coding* competition, after all. – rici Sep 13 '18 at 00:36
  • @rici This does shuffles but some permutations are more likely than others. – coder3101 Sep 13 '18 at 03:41
  • Yes, I understand that. So there are 4! possible permutations, not 4⁴. And `2,1,4,8` is not one of them. – rici Sep 13 '18 at 03:53
  • @rici I have taken 1 based indexes so 2,1,4,3 is from them. If you build a tree with all possibilities for shuffles using the above algorithm you will get 4^4 leaf nodes each having one of the 4! Permutations – coder3101 Sep 13 '18 at 03:57
  • There are 4⁴ possible code paths. Regardless, there are only 4! permutations. But whatever. Good luck with CodeChef. – rici Sep 13 '18 at 04:01
  • I already said that in a comment to one of your co-competitors. The pattern becomes obvious if you generate larger solutions. As I also said, I regard competitions where the solution can be hardcoded into the program to be somewhat ridiculous. Nonetheless, I'm not going to provide the answer while the competition is open. – rici Sep 13 '18 at 04:02
  • Thank you for your help. I wanted to know if there was a pattern in it. I do honour the competition and will not directly ask the solution. – coder3101 Sep 13 '18 at 04:06

0 Answers0