~一个有关算法的虚拟故事 (powered by rst2S5)
Authors: | ZoomQuiet+gdg[AT]gmail.com |
---|---|
URL: | http://s5.zoomquiet.io/140511-hoa6-start4game/ |
(^.^)
for i in seq:
product = (i[0]*100 + i[1]*10 + i[2]) * (i[3]*10 + i[4])
if product > maximum:
maximum = product
max_item = i
elif product == maximum:
max_item += ','+i
return max_item, maximum
def permute(seq):
result = []
for a in seq:
for b in seq:
for c in seq:
for d in seq:
for e in seq:
if a!=b and a!=c and a!=d and a!=e and \
b!=c and b!=d and b!=e and \
c!=d and c!=e and d!=e:
result.append(''.join([a,b,c,d,e]))
return result
def permute(seq):
l = len(seq)
if l == 1:
return [seq]
else:
res=[]
for i in range(len(seq)):
rest = seq[:i] + seq[i+1:]
for x in permute(rest):
res.append(seq[i:i+1] + x)
return res
seq = list("1234")
thelist = permute(seq)
thelist = [ ''.join(x) for x in thelist ]
print thelist
$ python permute2.py
['1234', '1243', '1324', '1342', '1423',
'1432', '2134', '2143', '2314',
'2341', '2413', '2431', '3124',
'3142', '3214', '3241', '3412', '3421',
'4123', '4132', '4213', '4231', '4312', '4321']
def permute(seq):
l = len(seq)
if l <= 2:
if l == 2: return [ seq, [seq[1], seq[0]] ]
else: return [seq]
else:
res=[]
for i in range(len(seq)):
rest = seq[:i] + seq[i+1:]
for x in permute(rest):
res.append(seq[i:i+1] + x)
return res
def calc(seq, where):
maximum, max_item = 0, []
for i in seq:
product = int(i[:where]) * int(i[where:])
if product > maximum:
maximum, max_item = product, i
elif product == maximum:
max_item += ','+ i
print "Maximum at", max_item, ",product", maximum
if __name__ == "__main__":
seq = [ "56789", "56798" ]
where = 3
calc(seq,where)
import sys, calc
seq = list(sys.argv[1])
where = int(sys.argv[2])
thelist = [ ''.join(x) for x in permute(seq) ]
Print 'Got', len(thelist), 'items.'
calc.calc(thelist, where)
$ time python permute3.py 56789 3
Got 120 items.
Maximum at 87596 ,product 84000
real 0m0.040s
user 0m0.030s
sys 0m0.010s
def getPerm(seq, index):
"Returns the <index>th permutation of <seq>"
seqc= list(seq[:])
seqn= [seqc.pop()]
divider= 2 # divider is meant to be len(seqn)+1, just a bit faster
while seqc:
index, new_index= index//divider, index%divider
seqn.insert(new_index, seqc.pop())
divider+= 1
return seqn
from permute4.py import permute
seq = list("1234")
for i in range(30):
print permute(seq, i)
$ python test.py
1234 1243 1324 1423 1342 1432 2134
2143 3124 4123 3142 4132 2314
2413 3214 4213 3412 4312 2341 2431
3241 4231 3421 4321 1234 1243
1324 1423 1342 1432
def getPerm(seq, index):
seqc= list(seq[:])
seqn= [seqc.pop()]
divider= 2
while seqc:
index, new_index= index/divider
, index%divider
seqn.insert(new_index, seqc.pop())
divider+= 1
return seqn
$ time cpython permute4.py 1234567 4
Got 5040 items.
Maximum at 6531742 ,product 4846002
real 0m0.389s
user 0m0.370s
sys 0m0.010s
Slackware / RedHat / Redflag / Mandrake / Debian / XP / NT2000|3|5 / DOS / Solaris/ AIX / Unicos / OSX ...
def permute(seq):
result = []
for i in seq:
seq1 = seq[:]
seq1.remove(i)
for j in seq1:
seq2 = seq1[:]
seq2.remove(j)
for l in seq2:
seq3 = seq2[:]
seq3.remove(l)
for m in seq3:
seq4 = seq3[:]
seq4.remove(m)
result.append(''.join([i,j,l,m,seq4[0]]))
return result
def genfunc(n):
head = """
def permute(seq0):
result = [] """
boiler = """
for counter%i in seq%i:
seq%i = seq%i[:]
seq%i.remove(counter%i)"""
for i in range(1,n):
space = ' '*i
head = head + boiler.replace('\n','\n'+space)%(i,i-1,i,i-1,i,i)
temp = ','.join([ 'counter%i'%(x) for x in range(1,n) ] + ["seq%i[0]"%(n-1)])
head = head + '\n' + space + " result.append(''.join([%s]))"%(temp)
return head + '\n return result\n'
import sys
functext = genfunc(len(sys.argv[1]))
print functext
exec(functext)
print dir()
thelist = permute(list(sys.argv[1]))
print 'Got', len(thelist), 'items.'
$ python permute5.py 12345 3
def permute(seq0):
result = []
for counter1 in seq0:
seq1 = seq0[:]
seq1.remove(counter1)
for counter2 in seq1:
seq2 = seq1[:]
seq2.remove(counter2)
for counter3 in seq2:
seq3 = seq2[:]
seq3.remove(counter3)
for counter4 in seq3:
seq4 = seq3[:]
seq4.remove(counter4)
result.append(''.join([counter1,counter2,counter3,counter4,seq4[0]]))
return result
['__builtins__', '__doc__', '__name__', 'calc', 'functext', 'genfunc',
'permute', 'sys']
Got 120 items.
...
result.append(''.join([counter1,counter2,counter3,counter4,seq4[0]]))
return result
['__builtins__', '__doc__', '__name__', 'calc', 'functext', 'genfunc',
'permute', 'sys']
Got 120 items.
...
import sys, calc
functext = genfunc(len(sys.argv[1]))
#print functext
exec(functext)
thelist = permute(list(sys.argv[1]))
print 'Got',len(thelist),'items.'
calc.calc(thelist,int(sys.argv[2]))
$ time cpython permute5.py 1234567 4
Got 5040 items.
Maximum at 6531742 ,product 4846002
real 0m0.213s
user 0m0.200s
sys 0m0.010s
[4321] [3421] [321] < [3241] [21] < [231]... [3214] [213]... [1] < [321]... [21] < [231]... [213]...
def permute(seq):
seqn = [seq.pop()]
while seq:
newseq = []
new = seq.pop()
#print "seq:",seq,'seqn', seqn ,'new', new
for i in range(len(seqn)):
item = seqn[i]
for j in range(len(item)+1):
newseq.append(''.join([item[:j]
, new
, item[j:]]))
seqn = newseq
#print 'newseq',newseq
return seqn
import sys, calc
seq = list(sys.argv[1])
where = int(sys.argv[2])
thelist = permute(seq)
print 'Got', len(thelist), 'items.'
calc.calc(thelist, where)
$ time cpython permute6.py 1234567 4
Got 5040 items.
Maximum at 6531742 ,product 4846002
real 0m0.167s
user 0m0.150s
sys 0m0.020s
Got 24 items.
[
'1234', '2134', '2314', '2341',
'1324', '3124', '3214', '3241',
'1342', '3142', '3412', '3421',
'1243', '2143', '2413', '2431',
'1423', '4123', '4213', '4231',
'1432', '4132', '4312', '4321'
]
def permute(seq):
seqn = [ seq.pop()+seq.pop() ] # 仅改此处
while seq:
newseq = []
new = seq.pop()
#print "seq:",seq,'seqn', seqn ,'new', new
for i in range(len(seqn)):
item = seqn[i]
for j in range(len(item)+1):
newseq.append(''.join([item[:j]
, new
, item[j:]]))
seqn = newseq
#print 'newseq',newseq
return seqn
def calc2(seq, where):
maximum, max_item = 0, []
for i in seq:
product = int(i[:where]) * int(i[where:])
if product > maximum:
maximum, max_item = product, i
elif product == maximum:
max_item += ','+i
rev = list(i)
rev.reverse() # 专门配合permute7.py
i = ''.join(rev)
product = int(i[:where]) * int(i[where:])
if product > maximum:
maximum, max_item = product, i
elif product == maximum:
max_item += ','+i
print "Maximum at", max_item, ",product", maximum
$ time python permute2.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902
real 0m46.478s
user 0m46.020s
sys 0m0.430s
$ time python permute3.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902
real 0m38.997s
user 0m38.600s
sys 0m0.400s
$ time python permute4.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902
real 0m33.845s
user 0m33.460s
sys 0m0.380s
$ time python permute5.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902
real 0m10.681s
user 0m10.530s
sys 0m0.150s
$ time python permute6.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902
real 0m8.279s
user 0m8.110s
sys 0m0.170s
$ time cpython permute7.py 123456789 5
Got 181440 items.
Maximum at 875319642 ,product 843973902
real 0m7.827s
user 0m7.650s
sys 0m0.180s
[4321] [3421] [321] < [3241] [21] < [231]... [3214] [213]... [1] < [321]... [21] < [231]... [213]...
def getPerm(seq, index):
seqc= list(seq[:])
seqn= [seqc.pop()]
divider= 2
while seqc:
index, new_index= index/divider
, index%divider
seqn.insert(new_index, seqc.pop())
divider+= 1
return seqn
# 假设五个数为 [a][b][c]*[d][e]
# 展开的话...
a * 100 * d * 10
+ a * 100 * e * 1
+ b * 10 * d * 10
+ b * 10 * e * 1
+ c * 1 * d * 10
+ c * 1 * e * 1
def solve(seq,where):
n = len(seq)
seq.sort()
seq.reverse()
table = [ [] for i in range(n) ]
left, right = where, n - where
leftr = long('1'*left) # 全1 的占位数值
rightr = long('1'*right)
flag=[] # 已经选好的位置
for item in [ int(x) for x in seq]:
for i in range(left):
table[left-i-1] = (leftr + 10**i) * rightr
for i in range(right):
table[right-i+where-1] = leftr * (rightr + 10**i)
for i in flag:
table[i] = 0
tablesorted = table[:]
tablesorted.sort()
maxindex = table.index(tablesorted[-1])
if maxindex >= where:
rightr = rightr + (item-1) * 10**(right-maxindex+where-1)
else:
leftr = leftr + (item-1) * 10**(left-maxindex-1)
flag.append(maxindex)
#print maxindex, leftr, rightr
return leftr, rightr
$time python permute7.py 123456789 5
Got 181440 items.
Maximum at 875319642 ,product 843973902
real 0m7.827s
user 0m7.650s
sys 0m0.180s
$ time python wise2.py 123456789 5
Maximum at 87531 9642 ,product 843973902
real 0m0.042s
user 0m0.010s
sys 0m0.030s
n!
Q&A
.
.
Authors: | ZoomQuiet+gdg[AT]gmail.com |
---|---|
URL: | http://s5.zoomquiet.io/140511-hoa6-start4game/ |
140508 调整细节,形成故事...
140507 增补代码,调节章节
140504 为HOA.6 创建
2002年许由 glace 整理到中蟒 Wiki 中
Authors: | ZoomQuiet+gdg[AT]gmail.com |
---|---|
URL: | http://s5.zoomquiet.io/140511-hoa6-start4game/ |