排列组合确实慢
牛逼嗷
学习学习
想知道
学习
本帖最后由 java2python 于 2020-6-3 01:16 编辑
达人的代码太精简了，里面的yield就不懂，用了他的conflict函数，写了一个非递归的：
def conflict(cur_row, row_ptr):
for i in range(cur_row):
if abs(row_ptr - row_ptr) in (0, cur_row - i):
return True
return False
def solve(QUEEN_SUM):
row_ptr = *QUEEN_SUM
cur_row = 0
while(True) :
while(row_ptr == QUEEN_SUM or conflict(cur_row,row_ptr)):
if(row_ptr == QUEEN_SUM):
cur_row -= 1
if(cur_row < 0 ):
return
row_ptr += 1
if(cur_row ==QUEEN_SUM-1) :
chest = [*QUEEN_SUM for i in range(QUEEN_SUM)]
for i in range(QUEEN_SUM):
chest] = 1
print (chest)
print ()
row_ptr += 1
else:
cur_row += 1
row_ptr = 0
solve(8)
yield看了网上的知识，还是半懂不懂，有点超出理解范围，做了一个没有yield的版本，对比代码，总算大致知道意思，yield是同一层的结果扔到turple后再return：
def conflict(state, nextX):
nextY = len(state)
for i in range(nextY):
if abs(state - nextX) in (0, nextY - i):
return True
return False
def queens(num = 3, state = (),cfloor=0):
res = None #这里要res要初始化
for pos in range(num):
if not conflict(state, pos):
#if len(state) == num - 1:
# yield (pos,)
if len(state) == num - 1:
return ((pos,),)
else:
#for result in queens(num, state + (pos,)):
# yield (pos,) + result
result = queens(num, state + (pos,),cfloor+1)
if result == None: #这里要None判别
continue
for ren in result:
if res == None: #这里要None判别
res = (((pos,) + ren),)
else:
res =(((pos,) + ren),) + res
return res
c = 0
result = queens(6,(),0)
for res in result:
c+=1
print ('Solution %d: ' % c)
chest = [*len(res) for i in range(len(res))]
for i in range(len(res)):
chest] = 1
print (chest)
print ()
本帖最后由 java2python 于 2020-6-2 14:51 编辑
八皇后全排列做法（一共是16777216组合，如果找到第一个布局就跳出，就10秒，全部的话3分多钟）：
pows =
def check(rows):
for row in range(1,8):
for i in range(row):
if abs(rows - rows) in (0, row - i):
return True
return False
rows = *8
for sts in range(0,pow(8,8)):
for bit in range(0,8):
rows=(sts%pows)//pows
if check(rows) == False:
chest = [*8 for i in range(8)]
for i in range(8):
chest] = 1
print (chest)
print ()
#break
当然全排列太慢了，不过可以稍作改进，就和快速搜索是一样速度了（当然每一位用pows取余数再除，会多一点时间，不过没有数量级的区别）,就是检测局面的时候，哪一行出问题（check函数返回true，false改为行号，如果是0，就是原来的false），那么就直接进入这一行的下一个选项（这一行已经出问题，后面的排列搜索全是无用功，实际逻辑和快速搜索一样，不过全排列的程序是最容易理解的）：
pows =
def check(rows):
for row in range(1,8):
for i in range(row):
if abs(rows - rows) in (0, row - i):
return row
return 0
rows = *8
sts = 0
while sts < pow(8,8):
for bit in range(0,8):
rows=(sts%pows)//pows
err_row = check(rows)
if err_row == 0:
chest = [*8 for i in range(8)]
for i in range(8):
chest] = 1
print (chest)
print ()
sts += 1
else:
sts += pows
那份开始开始疯狂
{:5_109:}
嗷嗷嗷
谢谢
要看
{:10_256:}
666
666
布耶特呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃
1