Randomly selecting a file from a tree of directories in a completely fair manner
<p>I'm looking for a way to randomly select a file from a tree of directories in a manner such that any individual file has exactly the same probability of being chosen as all other files. For example in the following tree of files, each file should have a 25% chance of being chosen:</p>

<ul>
<li>/some/parent/dir/
<ul>
<li>Foo.jpg</li>
<li>sub_dir/
<ul>
<li>Bar.jpg</li>
<li>Baz.jpg</li>
<li>another_sub/
<ul>
<li>qux.png</li>
</ul></li>
</ul></li>
</ul></li>
</ul>

<p>My interim solution which I'm using while I code the rest of the app is to have a function like so:</p>

<pre><code>def random_file(dir):
    file = os.path.join(dir, random.choice(os.listdir(dir)));
    if os.path.isdir(file):
        return random_file(file)
    else:
        return file
</code></pre>

<p>However this obviously biases the results depending on where they are in the tree and how many siblings are along side them in their directory so they end up with the following probabilities of being selected:</p>

<ul>
<li>/some/parent/dir/
<ul>
<li>Foo.jpg - 50%</li>
<li>sub_dir/ (50%)
<ul>
<li>Bar.jpg - 16.6%</li>
<li>Baz.jpg - 16.6%</li>
<li>another_sub/ (16.6%)
<ul>
<li>qux.png - 16.6%</li>
</ul></li>
</ul></li>
</ul></li>
</ul>

<p>The context for the function is in a background rotation app I'm writing, so the ability to filter out unwanted file extensions from being in the results would be a bonus (although I could simply force that by choosing again if it's not the file type I want... that gets messy if there's an abundance of files of the "wrong" type, though).</p>
