Setのパズル
集合演算
１．集合はダイナミック
このワークシートはMath by Codeの一部です。
集合というと、外延的定義と内包的定義の２種類の説明だったり、
ベン図をかいてその交わりや合併を見える化してみたり、
何か、止まったイメージがあるね。
でも、関数を使うことで、集合と集合がダイナミックにつながったり、生成したりするイメージが
わいてくる。
＜部分集合を作る関数＞
たとえば、部分集合というのがあるね。
４つの要素の集合があるとしたら、
その部分集合は、各要素を入れる/入れないを４回選べるので、
２の４乗通りの部分ができることは基本的なことだね。
極端でつまらない部分集合、自明な部分集合が２つあったね。
４つとも入らない∅
４つとも入る全集合
つまらないといっても、極端なことは数学では重要になることがある。
この２つが入ることで、きれいに２の要素数乗の部分集合があるといえるしね。
この部分集合たちを１つの集合と見ると、その個数は２のベキ乗になる。
そんなところから、この集合（部分集合の集合）をベキ集合と呼ぶこともあるね。
質問：集合から部分集合を作り出す関数はどうやって作ったらよいですか？
juliaで作るとしたらどうしよう。
たとえば、４要素の集合xsの部分集合を作りたかったら、
ターゲット(target)は、はじめは∅だけのリストにしよう。
xsの先頭要素itemを取り出す。
・そのターゲットのコピー（参照ではなくて、別メモリ上）res_sameを作る
・そのターゲットの各要素に、itemをつけたして上書きする。
・更新されたtargetに対して、もとのコピー(res_same)を連結して、倍要素数のリストにする。
xsの次の要素itemを取り出す。
上記３項目をやる。
これをxsの要素数length(xs)だけ繰り返そう。
[IN]julia
#============================================================
function makeSubList(xs)
target=[[]]
for id in 1:length(xs)
res_same = deepcopy(target) #copyや[=]では参照のみコピー
for item in target
push!(item, xs[id])
end
target=append!(target,res_same)
println(target)
end
return target
end
start=[1,2,3,4]
makeSubList(start)
#============================================================
[out]
Vector{Any}[[1], []]
Vector{Any}[[1, 2], [2], [1], []]
Vector{Any}[[1, 2, 3], [2, 3], [1, 3], [3], [1, 2], [2], [1], []]
Vector{Any}[[1, 2, 3, 4], [2, 3, 4], [1, 3, 4], [3, 4], [1, 2, 4], [2, 4], [1, 4], [4], [1, 2, 3], [2, 3], [1, 3], [3], [1, 2], [2], [1], []]
[18]:
16-element Vector{Vector{Any}}:
[1, 2, 3, 4]
[2, 3, 4]
[1, 3, 4]
[3, 4]
[1, 2, 4]
[2, 4]
[1, 4]
[4]
[1, 2, 3]
[2, 3]
[1, 3]
[3]
[1, 2]
[2]
[1]
[]
ただし、集合といいながら、順番のあるリストというデータ構造を利用したコードなので、
本物の集合では、残念ながら動かない。
start=Set([1,2,3,4])
makeSubList(start)
MethodError: no method matching getindex(::Set{Int64}, ::Int64)
Stacktrace:
[1] makeSubList(xs::Set{Int64})
@ Main ./In[18]:6
[2] top-level scope
@ In[21]:2
start=[1,2,3,4]
res=makeSubList(start)
Set(map(x->Set(x),res))
集合として扱いたいならば、
こうして、結果を集合の集合に直しとけばいいね。
2。集合のいいところ
集合というデータ構造は順番がないので、順次的な処理には向かない。
しかし、いいところがある。
それは、要素がユニークだということ。
そして、処理によってリストが変化していくときに、それを集合に直すことで、
使った要素を引き算して、残りのまだ使える要素を取り出したりできることだ。
質問：リストを集合にするにはどうしたらいい？
juliaではSet()という関数でできます。
#[IN]julia
#================================
lst=[1,1,2,2,3,3,4,5]
set=Set(lst)
#================================
[OUT]
Set{Int64} with 5 elements:
5
4
2
3
1
質問：使った要素を引き算して、残りの要素を取り出したいときはどうしますか？
たとえば、1から100までの整数の集合lstを作ります。
次に、１から100までの整数の目がでるサイコロを300回ふって出た目の集合usedを作ります。
２つの集合lst, usedの差setdiff()は、まだサイコロを300回ふっても出ていない目です。
#[IN]julia
#================================
lst=Set([x for x in 1:100])
used = Set(rand(1:100, 1,300))
setdiff(lst,used)
#================================
[OUT]
Set{Int64} with 6 elements:
32
91
84
76
49
38
毎回、結果が変わりますね。
＜集合演算の確認＞
２つのAとBの集合演算の関数を確認しておこう。
juliaではリストに対しても集合関数が使える。
ということは、リスト操作関数のときにも、思い出して使えるといいね。
A∩B：積集合（重なり）の関数
julia> intersect([1, 2, 3], [3, 4, 5])
1-element Vector{Int64}:
3
julia> (0, 0.0) ∩ (-0.0, 0)
1-element Vector{Real}:
0
A∪B：和集合（合併）の関数
julia> union([1, 2], [3])
3-element Vector{Int64}:
1
2
3
julia> (0, 0.0) ∪ (-0.0, NaN)
3-element Vector{Real}:
0
-0.0
NaN
AーB：差集合の関数
julia> setdiff([1,2,3], [3,4,5])
2-element Vector{Int64}:
1
2
A△B = (A−B)∪(B−A）：対称差(重なりを引いた残り）の関数
julia> symdiff([1,2,3], [3,4,5], [4,5,6])
3-element Vector{Int64}:
1
2
6
x∈ A：ｘが集合(リストでもよい）Aの要素である関数
julia> a = 1:3:20
1:3:19
julia> 4 in a
true
julia> x∈(4, a)
true
ｘ∉A：ｘが集合(リストでもよい）Aの要素でない関数
∉(x, A)
juliaはユニコードも演算子や関数に使えるので、数学記号で動く。
A ⊆ B：AがBの部分集合である関数
julia> issubset([1, 2], [1, 2, 3])
true
julia> [1, 2, 3] ⊆ [1, 2]
false
３．集合で覆面算を解く
＜覆面算を集合関数で解こう＞
覆面算
read + write + talk = skill
のすべての解を求めたいとしましょう。
質問：どんなところに目をつけてコードを作りますか。
文字に数字を入れる処理と入れた結果で等式が成り立つかチェックする処理にわけると
かきやすいです。
・覆面算では、同じ文字は同じ数字、別の文字は別の数字が入ります。
・覆面算でも、最上位r,w,t,sは０がこないけど、他の位は０がこれます。
・a,e,t,r,kは２回出てくるので、先に入れてしまいたい。
・一の位に目をつけると、d+e+k≡l(mod 10)だから、lとの関係でdも先にいれる。
・さらに考えると数や和の範囲はもっと絞られるけど、覆面算を正面から解くわけではないので、
あとはコードで調べるのもよいでしょう。
pythonやjuliaでは、順列や組み合わせのループ用のパッケージがあるので、コードがすっきりしますよ。
aetrkdliwsの10文字に０から９の10数字を割り当てるから順列をすべて割り当ててもよい。
それだと、ループを１０重にするよりはループが１つになりきれいにかけるけど、時間がかかりすぎるでしょう。無駄な調査を減らすために、ループを2段階にしてみるのもありだ。
・第１ループ
使える数字usable=[0,1,2,3,4,5,6,7,8,9]の集合setU=Set(usable)から６個を取り出した順列ｖの６要素をタプルにいれる。(a,e,t,r,k,d) = v
そして、tとrが０でないなら、lをd+e+kの一の位として、vの数字集合Set(v)とset([l])が被らない。
・第２ループ
残った数字、diffs=setdiff(setU,Set([a,e,t,r,k,d,l]))から残り３数字i,w,sをsetからArrayに直してから、順列ｐで埋めていく。
埋めたら等式チェックをして、成立したらカウントして表示することにしよう。
#[IN]julia
#=================================================
# REPL画面でCombinatoricsをインポートする必要がある。
# Pkg> add Combinatorics
# 順列も、このパッケージに入っている。
using Combinatorics
usable=[0,1,2,3,4,5,6,7,8,9]
setU=Set(usable)
cnt=0
function check(a,e,t,r,k,d,l,i,w,s)
global cnt
A=r*1000+e*100+a*10+d
B=w*10000+r*1000+i*100+t*10+e
C=t*1000+a*100+l*10+k
D=s*10000+k*1000+i*100+l*11
if A+B+C==D
cnt +=1
println("$A + $B + $C = $D")
end
end
for v in Combinatorics.permutations(usable,6)
(a,e,t,r,k,d) = v
if t!=0 && r!=0
l=(d+e+k) % 10
if ∉(l, Set([a,e,t,r,k,d]))
diffs=setdiff(setU,Set([a,e,t,r,k,d,l]))
iws =[ x for x in diffs]
for p in Combinatorics.permutations(iws)
(i,w,s) = p
if w!=0 && s!=0
check(a,e,t,r,k,d,l,i,w,s)
end
end
end
end
end
print("$cnt 通り")
#=================================================
[OUT]
4905 + 24689 + 8017 = 37611
9728 + 19467 + 6205 = 35400
1632 + 41976 + 7380 = 50988
2543 + 72065 + 6491 = 81099
5270 + 85132 + 3764 = 94166
5180 + 65921 + 2843 = 73944
5094 + 75310 + 1962 = 82366
5096 + 35710 + 1982 = 42788
7092 + 37510 + 1986 = 46588
7092 + 47310 + 1986 = 56388
10 通り