Anonymous user
Talk:Best shuffle: Difference between revisions
→On the Python "Swap if it is locally better algorithm"
(→Task Description: clear wording!) |
|||
Line 84:
::Never mind, I fixed it. --[[User:Rdm|Rdm]] 17:31, 7 January 2011 (UTC)
==On the Python "Swap if it is locally better algorithm"==
I had visited this problem around two weeks before and wrote a solution based on testing all permutations for the one with the best shuffle, but I could not wait for an answer when it was given 'abracadabra' and decided to 'sit on it'.
Today someone made an addition and I glanced through the AWK entry which mentioned swapping. That got me thinking of trying swapping characters and the first result of note that I came up with was:
<lang python>>>> def bs(w):
w2 = list(w)
rangew = range(len(w))
for i in rangew:
for j in rangew:
if i != j and w[i] != w[j]:
w2[j], w2[i] = w2[i], w2[j]
w2 = ''.join(w2)
return w2, count(w, w2)
>>> bs('elk')
('kel', 0)
>>> for w in 'tree abracadabra seesaw elk grrrrrr up a'.split():
print(w, bs(w))
tree ('reet', 1)
abracadabra ('aacrdrbaaab', 2)
seesaw ('seesaw', 6)
elk ('kel', 0)
grrrrrr ('rrgrrrr', 5)
up ('up', 2)
a ('a', 1)</lang>
I then thought that for better results I needed to go through the swapping twice; then multiple times - but that might loop forever so I added n, the maximum times through the for loops.
The condition on when to swap needed refinement too (- I never did check if this refinement would work without the need for the outer while loop?):
<lang python>>>> def bs(w):
w2 = list(w)
w2old = []
n = len(w)
rangew = range(n)
while w2old != w2 and n:
n -= 1
w2old = w2[:]
for i in rangew:
for j in rangew:
if i != j and w2[j] != w2[i] and w[i] != w2[j] and w[j] != w2[i]:
w2[j], w2[i] = w2[i], w2[j]
w2 = ''.join(w2)
return w2, count(w, w2)
</lang>
At this point I shoved this code in a file from the idle shell that I had been developing on, so intermediate results are harder to recreate.
The main changes developed in the file where to further refine the inner-most if statement determining when to swap. I then decided to add some randomness by the simple means of shuffling the range of integers that variables i and j iterate over.
Being as the code was nolonger based on testing all permutations, I gave it a word guaranteed to stress those types of solutions: ''antidisestablishmentarianism'' ;-) then just made sure it worked with the variety of words shown on the page, and tidied my output formatting. --[[User:Paddy3118|Paddy3118]] 08:38, 22 May 2011 (UTC)
| |||