title: Does this shuffling algorithm produce each permutation with uniform probability?
body: <p>I've seen how a particular naive shuffling algorithm is biased, and I feel like I basically get that, and I get how the Fischer-Yates algorithm is not biased.  I have the following algorithm which was the one I first thought of when I thought about how to shuffle a list.  I know it consumes twice the memory and runs in unnecessarily large time, but I'm still curious if it produces each permutation with a uniform distribution, or if there's some sneaky reason I'm not seeing for it to be biased.</p>
  
  <p>I'm also kind of wondering if there is some other "undesirable" property to a random shuffle that this would have, like perhaps the probabilities of various positions in the list being filled with some values are dependent.</p>
  
  <pre><code>def shuf(x):
      out = [None for i in range(len(x))]
      for i in x:
          pos = rand.randint(0,len(x)-1)
          while out[pos] != None:
              pos = rand.randint(0,len(x)-1)
          out[pos] = i
      return out
  </code></pre>
  
  <p>I generated a heat map of this on a list of 20 elements, running 10^6 trials, and it produced the following.  The (i,j) coordinate of the map represents the probability of the ith position of the list being filled with the jth element of the original list.</p>
  
  <p><img src="https://i.stack.imgur.com/PaIzO.png" alt="enter image description here"></p>
  
  <p>While I don't see any pattern to the heat map, it looks like the variance might be high.  Or that might be the heat map over-stating the variance because, hey, the minimum and max have to come up somewhere.</p>