魔方分割数
Posted feedbacks - Python
実装がナイーブ過ぎてN=4が実行できませんでした。 平均値計算の式が↓のようになっていて、これに気づくのに三十分かかった。 ave = N*(N*2+1) / 2 枝狩りをもうちょっとがんばるかなぁ。 アルゴリズムはこんな感じ。 １．総当りでペアを出す ２．ペアをソートする ３．文字列にキャストしてsetにぶち込んでユニーク化 ４．何個残ってるか？ コード書き終わってから、魔方陣の書き方って確かあったよなぁ。 と思って、Wikipedia先生に聞いてみたら二次元用であった。 これを応用すれば、うまいこと出てこないかなぁ。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | import copy
import time
def mahobunkatsu(N):
m = set()
for i in xrange(1,N**2+1):
m.add(i)
ave = N*(N**2+1) / 2
def createPair(restNumber,numberSum, pair, count, pairList):
for i in restNumber:
if count and (count+1)%N == 0:
if numberSum + i == ave:
if count+1 == N**2:
pair.append(i)
pairList.append(copy.copy(pair))
pair.pop()
continue
else:
continue
if numberSum + i > ave:
continue
restNumber.remove(i)
pair.append(i)
createPair(restNumber, (numberSum + i) % ave, pair, count + 1, pairList)
restNumber.add(i)
pair.pop()
return
pairList = []
createPair(m, 0, [], 0, pairList)
def listToSortedPairs(pairList):
temp = []
for l in pairList:
temp.append([])
for i in range(N):
temp[-1].append(l[i*N:(i+1)*N])
temp[-1][-1].sort()
temp[-1].sort()
return temp
sortedList = listToSortedPairs(pairList)
uniqueList = set()
for x in sortedList:
uniqueList.add(str(x))
print uniqueList
return uniqueList
t = time.time()
for x in range(2,6):
n = len(mahobunkatsu(x))
print "Size=",x,"Mahozin_num=",n,"time=",time.time()-t
t = time.time()
|
xsd
#4702()
Rating8/8=1.00
たとえば、N=3のときは、
(1) { 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }
(2) { 1, 6, 8 }, { 2, 4, 9 }, { 3, 5, 7 }
の2通りの方法があります。
ここで指定されたNに対して、何通りのグループ分けの方法があるかを数えるプログラムを作ってください。
(何通りかという値だけが出力されればよいのですが、予め計算してある結果を返すのはダメですよ。)
また、N=5を指定したときの実行時間もあわせて教えてください。
なお、数え上げるときの注意として、
・{ 1, 5, 9 } と { 1, 9, 5 }は同じもの
・{ 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }と
{ 1, 5, 9 }, { 3, 4, 8 }, { 2, 6, 7 }は同じもの
とすることに注意してください。
[ reply ]