1

I implemented the shuffling algorithm as:

import random
a = range(1, n+1) #a containing element from 1 to n
for i in range(n):
    j = random.randint(0, n-1)
    a[i], a[j] = a[j], a[i]

As this algorithm is biased. I just wanted to know for any n(n ≤ 17), is it possible to find that which permutation have the highest probablity of occuring and which permutation have least probablity out of all possible n! permutations. If yes then what is that permutation??

For example n=3:

a = [1,2,3]

There are 3^3 = 27 possible shuffle

No. occurence of different permutations:

1 2 3 = 4

3 1 2 = 4

3 2 1 = 4

1 3 2 = 5

2 1 3 = 5

2 3 1 = 5

P.S. I am not so good with maths.

Tom Ron
  • 5,906
  • 3
  • 22
  • 38
tanweer anwar
  • 117
  • 2
  • 7
  • this is not correct python syntax – dangee1705 Sep 11 '18 at 09:13
  • 3
    Possible duplicate of [why does this simple shuffle algorithm produce biased results? what is a simple reason?](https://stackoverflow.com/questions/859253/why-does-this-simple-shuffle-algorithm-produce-biased-results-what-is-a-simple) – r3mainer Sep 11 '18 at 10:20
  • 1
    I just have one very quick question how you get combination possible is 27, because if we go with basic permutation algo. possible combination for 3 values will go to 6, with factorial calculation. – Simmant Sep 11 '18 at 10:49
  • @Simmant 27 is the total number of different swaps which can be done for a list of length 3. For any i, j can be (0 to n-1), even i (in which case there will be no swap) – guroosh Sep 11 '18 at 12:14
  • and the [link](https://stackoverflow.com/questions/859253/why-does-this-simple-shuffle-algorithm-produce-biased-results-what-is-a-simple) given by @squeamishossifrage tells that it is possible to know which permutation has the least probability and can be calculated by looking at all the possibilities the random function goes and reaches the final permutation. – guroosh Sep 11 '18 at 12:25
  • @squeamishossifrage this question is slightly different. This [link](https://stackoverflow.com/questions/859253/why-does-this-simple-shuffle-algorithm-produce-biased-results-what-is-a-simple) explains why the algorithm is biased, on the other hand i just wants to know most probable and least probable result returned from the algorithm. – tanweer anwar Sep 11 '18 at 13:14
  • After some calculations I came to this conclusion, the original order is the most probable and the reverse order is the least. – guroosh Sep 11 '18 at 14:45
  • @gc7 when i ran the simulation for n < 8. I just got the opposite result. – tanweer anwar Sep 11 '18 at 15:24
  • how many iterations, i may be wrong – guroosh Sep 11 '18 at 15:34
  • @tanweeranwar OK, I see your point. I've retracted the close vote. – r3mainer Sep 11 '18 at 16:12
  • See https://stackoverflow.com/questions/52277314/most-and-least-favoured-permutation-in-naive-shuffle-algorithm?noredirect=1#comment91511396_52277314 for another duplicate of this one. Including in its comment a link to the programming competition that this is from. – btilly Sep 12 '18 at 22:35
  • Linked question referred to by btilly has been deleted. Programming competition link: [CodeChef September 2018 Challenge](https://www.codechef.com/SEPT18B/problems/BSHUFFLE) – rici Sep 14 '18 at 06:50

1 Answers1

0

This is not a proof by any means, but you can quickly come up with the distribution of placement probabilities by running the biased algorithm a million times. It will look like this picture from wikipedia:

permute with all order bias

An unbiased distribution would have 14.3% in every field.

To get the most likely distribution, I think it's safe to just pick the highest percentage for each index. This means it's most likely that the entire array is moved down by one and the first element will become the last.

Edit: I ran some simulations and this result is most likely wrong. I'll leave this answer up until I can come up with something better.

fafl
  • 7,222
  • 3
  • 27
  • 50
  • But that exactly is my problem. For **n > 7**, i can't run the program as to get an accurate answer in feasible time. So, is there any efficient way of doing this(for **n=9** i have to run the program at least 9^9 times, to get anyway near to theaccurate result). – tanweer anwar Sep 11 '18 at 12:58
  • You can use a Markov Chain algorithm to derive the probability by position chart like the one in Wikipedia; that would take O(n³) multiplications so it's practical for n=17. But the occupancy of different positions might not be independent of each other, so just taking the highest probability for each index might not be correct. Although I think it is, I don't have a proof. – rici Sep 11 '18 at 13:54
  • @rici can you explain how to implement Markov Chain Algorithm for this particular problem... – tanweer anwar Sep 11 '18 at 14:09
  • Actually, I was wrong. The highest probability permutation is not the one with the highest probability for each index. So the Wikipedia-style chart doesn't actually help you. Still, it would be a good way to learn about Markov Chains, if that is the intent of the course you are taking. – rici Sep 11 '18 at 14:40
  • 1
    @fafl: if I didn't make a mistake with a quick MC implementation over all permutations, the top two permutations for n=7 (the Wikipedia diagram) are (1, 2, 3, 0, 5, 6, 4) and (1, 2, 0, 4, 5, 6, 3), both with probability 543/7⁷. The next two are (1, 2, 3, 4, 0, 6, 5) and (1, 0, 3, 4, 5, 6, 2) with probability 504/7⁷. (1, 2, 3, 4, 5, 6, 0) has probability 429/7⁷. But my code could be completely out to lunch :) – rici Sep 11 '18 at 14:46
  • @rici actually you are correct, i got the same result for n=7 by running the simulations 10M times. But can't implement the same for any higher n. So can you elaborate on how you implemented MC. Btw this question is from a programming contest. – tanweer anwar Sep 11 '18 at 15:29
  • @tanweer: In the most naive way possible. Each Markov step takes as input the permutations and counts of the previous step. It applies the `n` possible swaps to each permutation, summing the result to produce permutation probabilities for the next step. That's O(n·n!) and you need n steps to get to the end. I summed counts rather than computing probabilities to avoid round-off errors; that won't be a problem until you reach bignum territory and that's out of range for this little Python program. n=10 took about 200 seconds on my laptop, but as I said to gc7 I was optimising for my time. – rici Sep 11 '18 at 15:33
  • @tanweer: By the way, the *least* likely permutation is the one which rotates one step to the left: (6, 0, 1, 2, 3, 4, 5). I think that's easy to prove analytically. It's probability is 2^(n-1)/n!. – rici Sep 11 '18 at 16:39
  • Prompted by btilly, I found [this old post](https://stackoverflow.com/questions/29354817/an-variant-of-knuth-shuffle/29379081#29379081) where I derived a closed-form for the probability table shown in Wikipedia. It doesn't help with the probability of permutations, at least not directly, but maybe it helps clarify thinking. Or maybe it's just confusing :) – rici Sep 11 '18 at 17:29
  • @fafl: here's a hint: rotations are important. Honestly, I'm amazed at how much I've forgotten about this little problem. I found my notes from a few years ago and it all clicked back into place :-( – rici Sep 11 '18 at 18:34