|
|
|
|
|
|
| Author |
Message |
Boris Borcic
*nix forums addict
Joined: 18 Apr 2006
Posts: 52
|
 Posted: Fri Jul 21, 2006 11:11 am Post subject:
random shuffles
|
|
|
does
x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
pick a random shuffle of x with uniform distribution ?
Intuitively, assuming list.sort() does a minimal number of comparisons to
achieve the sort, I'd say the answer is yes. But I don't feel quite confortable
with the intuition... can anyone think of a more solid argumentation ?
- BB
--
"On naît tous les mètres du même monde" |
|
| Back to top |
|
 |
Peter Otten
*nix forums Guru
Joined: 20 Feb 2005
Posts: 464
|
| Posted: Fri Jul 21, 2006 11:32 am Post subject:
Re: random shuffles
|
|
|
Boris Borcic wrote:
| Quote: | does
x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
pick a random shuffle of x with uniform distribution ?
Intuitively, assuming list.sort() does a minimal number of comparisons to
achieve the sort, I'd say the answer is yes. But I don't feel quite
confortable with the intuition... can anyone think of a more solid
argumentation ?
|
Anecdotal evidence suggests the answer is no:
| Quote: | histo = {}
for i in xrange(1000):
.... t = tuple(sorted(range(3), lambda x, y: cmp(random.random(), 0.5))) |
.... histo[t] = histo.get(t, 0) + 1
....
| Quote: | sorted(histo.values())
[60, 62, 64, 122, 334, 358] |
versus:
| Quote: | histo = {}
for i in xrange(1000):
.... t = tuple(sorted(range(3), key=lambda x: random.random())) |
.... histo[t] = histo.get(t, 0) + 1
....
| Quote: | sorted(histo.values())
[147, 158, 160, 164, 183, 188] |
Peter |
|
| Back to top |
|
|
Dustan
*nix forums beginner
Joined: 21 Nov 2005
Posts: 36
|
| Posted: Fri Jul 21, 2006 12:22 pm Post subject:
Re: random shuffles
|
|
|
Boris Borcic wrote:
| Quote: | does
x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
pick a random shuffle of x with uniform distribution ?
Intuitively, assuming list.sort() does a minimal number of comparisons to
achieve the sort, I'd say the answer is yes. But I don't feel quite confortable
with the intuition... can anyone think of a more solid argumentation ?
|
Why not use the supplied shuffle method?
random.shuffle(x) |
|
| Back to top |
|
|
Iain King
*nix forums addict
Joined: 16 Sep 2005
Posts: 70
|
| Posted: Fri Jul 21, 2006 12:34 pm Post subject:
Re: random shuffles
|
|
|
Dustan wrote:
| Quote: | Boris Borcic wrote:
does
x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
pick a random shuffle of x with uniform distribution ?
Intuitively, assuming list.sort() does a minimal number of comparisons to
achieve the sort, I'd say the answer is yes. But I don't feel quite confortable
with the intuition... can anyone think of a more solid argumentation ?
Why not use the supplied shuffle method?
random.shuffle(x)
|
or check out this thread:
http://groups.google.com/group/comp.lang.python/browse_thread/thread/766f4dcc92ff6545?tvc=2&q=shuffle
Iain |
|
| Back to top |
|
|
Tim Peters
*nix forums Guru Wannabe
Joined: 26 Feb 2005
Posts: 192
|
| Posted: Fri Jul 21, 2006 1:18 pm Post subject:
Re: random shuffles
|
|
|
[ Boris Borcic]
| Quote: | x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
pick a random shuffle of x with uniform distribution ?
|
Say len(x) == N. With Python's current sort, the conjecture is true
if and only if N <= 2.
| Quote: | Intuitively, assuming list.sort() does a minimal number of comparisons to
achieve the sort,
|
No idea what that could mean in a rigorous, algorithm-independent way.
| Quote: | I'd say the answer is yes. But I don't feel quite confortable
with the intuition... can anyone think of a more solid argumentation ?
|
If a list is already sorted, or reverse-sorted, the minimum number of
comparisons needed to determine that is N-1, and Python's current sort
achieves that. It first looks for the longest ascending or descending
run. If comparison outcomes are random, it will decide "yes, already
sorted" with probability 1/2**(N-1), and likewise for reverse-sorted.
When N > 2, those are larger than the "correct" probabilities 1/(N!).
So., e.g., when N=3, the sort will leave the list alone 1/4th of the
time (and will reverse the list in-place another 1/4th). That makes
the identity and reversal permutations much more likely than "they
should be", and the bias is worse as N increases.
Of course random.shuffle(x) is the intended way to effect a
permutation uniformly at random. |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Nov 22, 2008 9:26 pm | All times are GMT
|
|
Mortgage Calculator | Consolidate Student Loans | Adverse Credit Remortgage | Mobile Phones | Loans
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
|
|
Other DeniX Solutions sites:
Unix/Linux blog |
electronics forum |
medicine forum |
science forum |
|
|
Privacy Policy
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Programming
»
python
