東方の海

サブカル考察など。

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
--.--.-- --:-- | スポンサー広告 | トラックバック(-) | コメント(-) |

最近Twitterで話題になった数学の未解決問題で筆者が取り組んでいる問題に、プリクラ問題というのがあります。

という問題提起から始まったものです。Togetterまとめは以下。

プリクラ問題 - Togetterまとめ

プリクラ問題2

プリクラ問題まとめのまとめ - Togetterまとめ


---以上、2016年5月31日追記。---


プリクラ問題の総探索プログラムのRubyコードをおいておきます。

def solve(n,m) #プリクラ問題。n人がm人まで入れるプリクラで全員自分以外の人と1回以上撮るためのプリクラ撮影回数の最小値を求める。
mincount = C(n,m)
card = card(n,m)
order = order(C(n,m))
order.each{|elem| mincount=min(mincount,count(card,elem))}
return mincount
end
def count(card,order) #cardをorder順にparseしてcard使用回数を数えて返す関数
flag = make2d(order.length(),order.length())
counter = 0
for i in 0..(order.length()-1)
counter = counter + 1
parse(card[order[i]-1]).each{|elem| flag[elem[0]-1][elem[1]-1]=1}
if (sumElem(sumElem(flag)) == C(order.length(),2))
break
end
end
return counter
end
def parse(a) #[3,1,2]を代入すると[[3,1],[3,2],[1,2]]を返すような関数
deck = make1d(C(a.length(),2))
count = 0
for i in 0..(a.length()-1)
for j in (i+1)..(a.length()-1)
deck[count] = [a[i]] + [a[j]]
count = count + 1
end
end
return deck
end
def order(n) #[[1,2,3],..,[3,2,1]]を返すような関数
deck = make1d(P(n,n))
line = make1d(n)
for i in 0..(n-1)
line[i] = i + 1
end
counter = [0]
def shuffle(orig,count,a,b=[]) #配列の要素を順番に抜き出す再帰的関数
if a.length() == 0
orig[count[0]] = b
count[0] = count[0] + 1
else
a.each{|i| shuffle(orig,count,a-[i],b+[i])}
end
end
shuffle(deck,counter,line)
return deck
end
def card(n,m) #[[1,2,3],..,[3,4,5]]を返すような関数
deck = make1d(C(n,m))
temp = deck.clone
temp[0] = make1d(m)
for i in 0..(m-1)
temp[0][i] = i+1
end
deck[0] = temp[0].clone
def pointer(n,m,narray,num) #[1,4,5]を代入すると[2,3,4]を返すような関数
if num > -1
if narray[num] < n+num+1-m
narray[num] = narray[num]+1
if num < m-1
for i in 1..(m-1-num)
narray[num+i] = narray[num]+i
end
end
return narray
else
pointer(n,m,narray,num-1)
end
else
return 'error: the last elem [n-m+1,..,n] was put in pointer().'
end
end
for i in 1..C(n,m)-1
temp[i] = pointer(n,m,temp[i-1],m-1)
deck[i] = temp[i].clone
end
return deck
end
def max(x,y) #x,yのうち大きい方を返す
if x >= y
x
else
y
end
end
def min(x,y) #x,yのうち小さい方を返す
if x <= y
x
else
y
end
end
def maxElem(a,i=a.length()-1) #0..iの配列aのうち最大の要素を返す
if i==0
a[0]
else
if maxElem(a,i-1) > a[i]
maxElem(a,i-1)
else
a[i]
end
end
end
def minElem(a,i=a.length()-1) #0..iの配列aのうち最小の要素を返す
if i==0
a[0]
else
if minElem(a,i-1) > a[i]
a[i]
else
minElem(a,i-1)
end
end
end
def sumElem(a,i=a.length()-1) #配列の要素の合計を返す
if i==0
a[0]
else
a[i] + sumElem(a,i-1)
end
end
def make1d(n) #長さnの零列ベクトルを返す
a = Array.new(n)
for i in 0..(n-1)
a[i] = 0
end
a
end
def make2d(height,width) #height行witdth列の行列を返す
a = Array.new(height)
for i in 0..(height-1)
a[i] = make1d(width)
end
a
end
def C(n,k) #nCkを返す
if k > n
0
else
if k == 0
1
else
C(n-1,k-1)+C(n-1,k)
end
end
end
スポンサーサイト
2016.03.08 01:40 | 数学 | トラックバック(-) | コメント(0) |












管理者にだけ表示

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。