rscのブログ (original) (raw)

知恵袋で見つけた同じものを含む円順列の問題をPythonで解いてみました。これは難問らしいです。(^_^;

赤玉6個と白玉6個を円形に並べる際の場合の数

同じものを含む順列でも総数が大きくなると、「set(itertools.permutation())」では遅くなるので、Java から Python に翻訳して作った genPerm()関数を使いました。(^_^;
ちなみに、同じものを含む円順列には公式があるようです。(cf.参考URL)

● CircularPerm2.py

from time import time

def nextPerm(p, n, r): i = j = 0 if r <= 0 or n < r : return False for i in range(r+1,n): for j in range(i,r,-1): if not p[j-1] < p[j]: break p[j], p[j-1] = p[j-1], p[j] for i in range(n-1,0,-1): if not p[i-1] >= p[i]: break else: i-=1 if i==0: return False for j in range(n-1,i,-1): if not p[i-1] >= p[j]: break else: j-=1 p[i-1], p[j] = p[j], p[i-1] j = n-1 while i < j: p[i], p[j] = p[j], p[i] i+=1; j-=1 return True

def genPerm(p,r=0): n = len(p) if r==0: r = n q = p[:]; q.sort() while True: yield q if not nextPerm(q,n,r): break

def main(): tm = time() P = '赤'*6+'白'6 s = ''
cnt = 0 for p in genPerm(list(P)):
t = ''.join(p) if t not in s: cnt+=1 print(t) s+=t2+'|'

print(f'計: {cnt}')
print(f'Runtime : {time()-tm:.3f} [sec]')

if name == 'main': main()

●実行結果

白白白白白白赤赤赤赤赤赤 白白白白白赤白赤赤赤赤赤 白白白白白赤赤白赤赤赤赤 …(省略)… 白白赤赤白赤白白赤赤白赤 白白赤赤白赤白赤白赤白赤 白赤白赤白赤白赤白赤白赤 計: 80 Runtime : 0.016 [sec]

※参考URL
●同じものを含む円順列の総数（julia版）
●完全順列，全射，円順列の総数
●同じものを含む円順列の問題をPythonで解いてみた。 - rscのブログ
●知恵袋で見つけた赤玉と白玉の組分けの問題をPythonで解いてみた。 - rscのブログ
●同じものを含む数珠順列の問題をJavaで解いてみた。 - rscのブログ

スッキリわかるPython入門 第2版 (スッキリわかる入門シリーズ)

知恵袋で見つけた同じものを含む円順列の問題をPythonで解いてみました。(^_^;

赤玉2個、青玉2個、白玉4個を円形に並べる方法の総数を求めよ。

拙ブログのNecklacePerm01.javaを参考にして作りました。
場合の数・確率の問題は、検算が難しいため、答えに確信が持てないことが多いですね。(^_^;

● CircularPerm1.py

import itertools from time import time

def main(): tm = time() P = '赤赤青青白白白白' s = ''
cnt = 0 for p in sorted(set(itertools.permutations(P))):
t = ''.join(p) if t not in s: cnt+=1 print(t) s+=t+t+'|'

print(f'計: {cnt}')
print(f'Runtime : {time()-tm:.3f} [sec]')

if name == 'main': main()

●実行結果

白白白白赤赤青青 白白白白赤青赤青 白白白白赤青青赤 …(省略)… 白白青青白赤白赤 白赤白赤白青白青 白赤白青白赤白青 計: 54 Runtime : 0.016 [sec]

※参考URL
●同じものを含む数珠順列の問題をJavaで解いてみた。 - rscのブログ
●- YouTube
●同じものを含む円順列の問題をPythonで解いてみた。(2) - rscのブログ

スッキリわかるPython入門 第2版 (スッキリわかる入門シリーズ)

前回の続きです。今回は、前回の問題を順列を使わずに解いてみました。(^_^;
人をまとまって動く「A～EとL」、「G～J」、「FとK」の3つのグループに分け、自力で解くときのようにピクチャーパズルを解くような感じで作ってみました。(^_^;
A,H,Fを、それぞれ位置検索用マップの 0～b の範囲で動かして、自身とそのグループのメンバーが置けるかどうか調べていきました。置けるかどうかの判定は、置く場所に作成用マップのピリオド「.」がまだ残っているかどうかで調べました。
実行時間は、かなり速くなりましたが、プログラムを作るのに時間がかかるので、結局、自力で解いた方が早いです。でも、検算の代わりにはなるのかなぁ。(^_^;

● seating5.py

import itertools from time import time

RM, CM = 3+2, 4+2

MAP = ''' ###### #0123# #4567# #89ab# ###### ''' MAP = MAP.replace('\n','')

MAP0 = ''' ###### #....# #....# #....# ###### ''' MAP0 = MAP0.replace('\n','')

def getRow(n): return n//CM

def getCol(n): return n%CM

def getN(r,c): if not(0<=r< RM): return -1
if not(0<=c< CM): return -1 return r*CM+c

def getFrontOf(c, map): n = map.index(c) r,c = getRow(n),getCol(n) return map[getN(r-1,c)]

def getBackOf(c, map): n = map.index(c) r,c = getRow(n),getCol(n) return map[getN(r+1,c)]

def mkNewMap(mp,li,names): r = mp for i,n in enumerate(li): r = subStr(r,n,1,names[i]) return r

def subStr(s,m,n,t=None): if t is None: return s[m:m+n] return f'{s[:m]}{t}{s[m+n:]}'

def PrintResult(c,m): print(f"[{c:2d}]") print(f"{m[ :CM ]}") print(f"{m[CM :CM2]}") print(f"{m[CM2:CM3]}") print(f"{m[CM3:CM4]}") print(f"{m[CM4: ]}")

def getAns(ch,lb='12345'): return ','.join([lb[i] for i,c in enumerate(ch) if c])

def main(): tm = time() choices = [True]*5 PLACE = '0123456789ab' P = 'ABCDEL'
Q = 'GHIJ'
R = 'FK'
count = 0 Maps = [] m = MAP0 for nA in range(12): a = MAP.index(PLACE[nA])
for b,c in [(a-1,a+1),(a+1,a-1)]:
if m[b]!='.' or m[c]!='.': continue
d = getN(getRow(b)+1,getCol(b))
if m[d]!='.': continue
e = getN(getRow(c)-1,getCol(c))
if m[e]!='.': continue
for l in (d-1,d+1): if m[l]!='.': continue
pass m1 = mkNewMap(m,[a,b,c,d,e,l],P)
Maps.append(m1)

for m in Maps:
    for nH in range(12):
        h = MAP.index(PLACE[nH])            
        if m[h]!='.': continue
        for g,i in [(h-1,h+1),(h+1,h-1)]:   
            if m[g]!='.' or m[i]!='.': continue     
            j = getN(getRow(g)+1,getCol(g)) 
            if m[j]!='.': continue                  
            pass 
            m1 = mkNewMap(m,[g,h,i,j],Q)

            for nF in range(12):
                f = MAP.index(PLACE[nF])    
                if m1[f]!='.': continue
                for k in (f-1,f+1):
                    if m1[k]!='.': continue         
                    pass 
                    m2 = mkNewMap(m1,[f,k],R)
                    count+=1
                    PrintResult(count,m2)
                    
                    choices[0] &= getBackOf('A',m2)=='F'
                    choices[1] &= ('EG' in m2 or 'GE' in m2)
                    choices[2] &= getBackOf('H',m2)=='A'
                    choices[3] &= ('KB' in m2 or 'BK' in m2)
                    choices[4] &= getFrontOf('L',m2)=='J'

print("∴%s"%getAns(choices))
print("Runtime : %.3f [sec]"%(time()-tm))

if name == 'main': main()

●実行結果

[ 1] ###### #EIHG# #CABJ# #FKDL# ###### [ 2] ###### #EIHG# #CABJ# #KFDL# ###### [ 3] ###### #GHIE# #JBAC# #LDFK# ###### [ 4] ###### #GHIE# #JBAC# #LDKF# ###### ∴5 Runtime : 0.000 [sec]

※参考URL
●質問の座席の問題をPythonで解いてみた。 - rscのブログ
●知恵袋の判断推理の座席の位置関係の問題をPythonで解いてみた。 - rscのブログ
●判断推理の座席の位置関係の問題をPythonで解いてみた。 - rscのブログ
●判断推理の座席の位置関係の問題をPythonで解いてみた。(2) - rscのブログ

スッキリわかるPython入門 第2版 (スッキリわかる入門シリーズ)

論理パズル101―推理の楽しさ、ひらめきの快感 (ブルーバックス)

ネットで見つけた判断推理の座席の位置関係の問題をPythonで解いてみました。(^_^;

図のように机が配置されている教室で、黒板に向かって座っているA～Lの12人の生徒の席順について、次のア～キのことが分かっている。
ア Aの両隣にはBとCが座っている。
イ Bのすぐ後ろにはDが座っている。
ウ Cのすぐ前にはEが座っている。
エ Dの隣にはLが座っている。
オ Fの隣にはKが座っている。
カ Gのすぐ後ろにはJが座っている。
キ Hの両隣にはGとIが座っている。
以上から判断して、確実にいえるのはどれか。
１ Aのすぐ後ろにはFが座っている。
２ Eの隣にはGが座っている。
３ Hのすぐ後ろにはAが座っている。
４ Kの隣にはBが座っている。
５ Lのすぐ前にはJが座っている。

+------------------+ | ============== | | 黒板 | | [ 0][ 1][ 2][ 3] | | ◎ ◎ ◎ ◎ | | [ 4][ 5][ 6][ 7] | | ◎ ◎ ◎ ◎ | | [ 8][ 9][10][11] | | ◎ ◎ ◎ ◎ | +------------------+

（注）◎は各生徒の座席位置を示す

ただし、各座席に0～11の通し番号を付けました。
12個の順列は時間がかかるので枝が早く刈れそうなA～Eのグループと残りのグループに分け、A～Eのグループだけのマップを先に作成して、残りを順列で回してみました。(^_^;
前半のA～Eのグループだけのマップを作成する場合、同じものを含む順列を使ってもいいですが、「set(itertools.permutations())」は、
全要素数が大きいと遅くなってしまうようなので、結果の出力数が少ないと速くなる拙ブログのPermSame1.pyで用いた「genPerm()」を使うとよいです。(^_^;
ちなみに、subStr()関数は、Perlのsubstr()関数を参考にして作りました。ただし、Perlと違って、文字列 s は、変更せずに、置換後の文字列は、戻り値として返します。(^_^;

● seating4.py

import itertools from time import time

RM, CM = 3+2, 4+2

MAP = ''' ###### #0123# #4567# #89ab# ###### ''' MAP = MAP.replace('\n','') MAP1 = '#'*CM+'#....#'*3+'#'*CM

def getRow(n): return n//CM

def getCol(n): return n%CM

def getN(r,c): if not(0<=r< RM): return -1
if not(0<=c< CM): return -1 return r*CM+c

def getFrontOf(c, map): n = map.index(c) r,c = getRow(n),getCol(n) return map[getN(r-1,c)]

def getBackOf(c, map): n = map.index(c) r,c = getRow(n),getCol(n) return map[getN(r+1,c)]

def mkNewMap(m,p): r = m li = LookUp('.',r) for i,n in enumerate(li): r = subStr(r,n,1,p[i]) return r

def LookUp(x,la,lb=[]): if lb==[]: return [i for i,a in enumerate(la) if a==x] return [lb[i] for i,a in enumlate(la) if a==x]

def subStr(s,m,n,t=None): if t is None: return s[m:m+n] return f'{s[:m]}{t}{s[m+n:]}'

def PrintResult(c,m): print(f"[{c:2d}]") print(f"{m[ :CM ]}") print(f"{m[CM :CM2]}") print(f"{m[CM2:CM3]}") print(f"{m[CM3:CM4]}") print(f"{m[CM4: ]}")

def getAns(ch,lb='12345'): return ','.join([lb[i] for i,c in enumerate(ch) if c])

def main(): tm = time() choices = [True]*5 PLACE = '0123456789ab' P = 'ABCDE'
Q = 'FGHIJKL'
count = 0 Maps = [] for i in range(12): a = MAP.index(PLACE[i])
for b,c in [(a-1,a+1),(a+1,a-1)]:
if '#' in (MAP[b], MAP[c]): continue
d = getN(getRow(b)+1,getCol(b))
if MAP[d]=='#': continue
e = getN(getRow(c)-1,getCol(c))
if MAP[e]=='#': continue
pass m = MAP1
for i,n in enumerate([a,b,c,d,e]): m = subStr(m,n,1,P[i]) Maps.append(m)

for p in Maps:
    for q in itertools.permutations(Q):
        m = mkNewMap(p,q)
        if not ('DL' in m or 'LD' in m): continue   
        if not ('FK' in m or 'KF' in m): continue   
        if not getBackOf('G',m)=='J': continue      
        if not ('GHI' in m or 'IHG' in m): continue 
        pass 
        count+=1
        PrintResult(count,m)
        
        choices[0] &= getBackOf('A',m)=='F'
        choices[1] &= ('EG' in m or 'GE' in m)
        choices[2] &= getBackOf('H',m)=='A'
        choices[3] &= ('KB' in m or 'BK' in m)
        choices[4] &= getFrontOf('L',m)=='J'

print("∴%s"%getAns(choices))
print("Runtime : %.3f [sec]"%(time()-tm))

if name == 'main': main()

●実行結果

[ 1] ###### #EIHG# #CABJ# #FKDL# ###### [ 2] ###### #EIHG# #CABJ# #KFDL# ###### [ 3] ###### #GHIE# #JBAC# #LDFK# ###### [ 4] ###### #GHIE# #JBAC# #LDKF# ###### ∴5 Runtime : 0.551 [sec]

※参考URL
●質問の座席の問題をPythonで解いてみた。 - rscのブログ
●知恵袋の判断推理の座席の位置関係の問題をPythonで解いてみた。 - rscのブログ
●判断推理の座席の位置関係の問題をPythonで解いてみた。 - rscのブログ

スッキリわかるPython入門 第2版 (スッキリわかる入門シリーズ)

判断推理の座席の位置関係の問題をPythonで解いてみました。(^_^;

図のように、列車のボックスシートにＡ～Ｈの各４人ずつの男女、合わせて８人が向かい合わせに座っている。８人は、車内販売でコーヒー、オレンジジュース、野菜ジュース、緑茶の４種類の飲み物から一つずつ購入した。ア～キのことが分かっているとき、確実にいえるのはどれか。

+------ ------+ 窓| 通 |窓 | 路 |
側|(A)[ ]側( )[ ]|側 +------ ------+ []:男性,():女性

ア 男性４人が購入したものは互いに異なっており、女性４人が購入したものも互いに異なっていた。
イ 図において、右側のボックスシートの４人、左側のボックスシートの４人、通路側の席の４人が購入した飲み物は、それぞれ互いに異なっていた。
ウ Ａは図に示す席に座っており、Ａからみて右隣の人はコーヒーを購入した。
エ Ｂは通路側であり、通路を挟んでＢの隣はＣである。Ｃの向かいは女性で、その女性はオレンジジュースを購入した。
オ Ｃが購入したものはコーヒーではなかった。
カ ＤとＥは女性である。
キ Ｄはコーヒーを購入し、Ｈは野菜ジュースを購入した。

１ Ａの向かいはＦである。
２ Ｅの向かいの人は野菜ジュースを購入した。
３ ＧとＨは窓側である。
４ オレンジジュースを購入した人の向かいの人は緑茶を購入した。
５ 野菜ジュースを購入した人からみて左側の人はコーヒーを購入した。

上段と下段は向かい合っているので、左隣・右隣の条件を考えやすくするために、次のように座席番号を付けました。

+------#------+ |7#5| |(0)[1]#(2)[3]| +------#------+

拙ブログのseating2.pyを雛形にして作りました。また、選択肢４、５の「オレンジジュースを購入した人」や「野菜ジュースを購入した人」は、二人ずついるので、拙ブログのperm2row.pyから、LookUp()関数を持って来て使いました。(^_^;
ちなみに、「t = list(q)+['|']」は、seatNoA()関数が-1を返したときの対策です。(^_^;

● seating3.py

import itertools from time import time

def seatNo(c,p): return p.index(c)

def seatNoF(c,p): i = p.index(c) return 7-i

def isFemale(n): return n%2==0

def seatNoA(c,p,n): s = '|%s%s#%s%s|%s%s#%s%s|'%p
r = s[s.index(c)+n] if r in '|#': return -1 return p.index(r)

def LookUp(x,la,lb): return [lb[i] for i in range(len(la)) if la[i]==x]

def PrintResult(c,p,q): r = list(zip(p,q)) r1 = tFlatten(r[:4]) r2 = tFlatten(list(reversed(r[4:]))) print(f"[{c:2d}]") print("|%s:%s#%s:%s|"%r2) print("|(%s:%s)[%s:%s]#(%s:%s)[%s:%s]|"%r1)

def tFlatten(li): return tuple(itertools.chain.from_iterable(li))

def getAns(cho,lbl='12345'): return ','.join([lbl[i] for i in range(len(cho)) if cho[i]])

def main(): tm = time() choices = [True]*5 P = 'ABCDEFGH'
Q = 'ccoovvtt'
count = 0 for p in itertools.permutations(P): if not p[0]=='A': continue
s = '|%s%s#%s%s|%s%s#%s%s|'%p
if not ('B#C' in s or 'C#B' in s): continue
if not isFemale(seatNoF('C',p)): continue
if not isFemale(seatNo ('D',p)): continue
if not isFemale(seatNo ('E',p)): continue
for q in set(itertools.permutations(Q)): if len(set([q[1],q[3],q[5],q[7]]))!=4:continue
if len(set([q[0],q[2],q[4],q[6]]))!=4:continue
if len(set([q[0],q[1],q[6],q[7]]))!=4:continue
if len(set([q[2],q[3],q[4],q[5]]))!=4:continue
if len(set([q[1],q[2],q[5],q[6]]))!=4:continue
t = list(q)+['|']
if not t[seatNoA('A',p,1)]=='c': continue
if not t[seatNoF('C',p)]=='o': continue
if not t[seatNo ('C',p)]!='c': continue
if not t[seatNo ('D',p)]=='c': continue
if not t[seatNo ('H',p)]=='v': continue
pass count+=1 PrintResult(count,p,q)

        choices[0] &= p[seatNoF('A',p)]=='F'
        choices[1] &= t[seatNoF('E',p)]=='v'
        choices[2] &= ('|G' in s) or ('G|' in s)
        choices[2] &= ('|H' in s) or ('H|' in s)
        x,y = LookUp('o',q,p)
        choices[3] &= t[seatNoF(x,p)]=='t'
        choices[3] &= t[seatNoF(y,p)]=='t'
        x,y = LookUp('v',q,p)
        choices[4] &= t[seatNoA(x,p,-1)]=='c'
        choices[4] &= t[seatNoA(y,p,-1)]=='c'

print("∴%s"%getAns(choices))
print("Runtime : %.3f [sec]"%(time()-tm))

if name == 'main': main()

●実行結果

[ 1] |G:o#C:t| |(A:t)[F:c]#(E:o)[H:v]| [ 2] |F:o#C:t| |(A:t)[G:c]#(E:o)[H:v]| ∴4 Runtime : 0.355 [sec]

※参考URL
●質問の座席の問題をPythonで解いてみた。 - rscのブログ
●知恵袋の判断推理の座席の位置関係の問題をPythonで解いてみた。 - rscのブログ

スッキリわかるPython入門 第2版 (スッキリわかる入門シリーズ)

ブログのデザインを変更してみました。サイドバーに「カテゴリー」を追加しました。備忘録代わりにやり方をメモしておきます。(^_^;
右上の右端「アカウント設定」→「ブログを管理」→ダッシュボード「デザイン」とクリックしていき、続いて、左上の左から２番目スパナのアイコン「カスタマイズ」→全般の「サイドバー」をクリックして、「モジュールを追加」→左側から「カテゴリー」をクリックしました。
「並び変え順」を「記事が追加された順」に変更して、「適用」をクリックして、左上の「変更を保存する」をクリックしました。