route127の日記： 3種の数字から5桁の数字を生成する行列みたいな感じ 7
3種の数字で作られる4桁の数は何通りかの続きというか発展というか。
むしろ雪辱戦か？
というのもなんとなくgrep最強説で締めくくられた感じがあって、まあ実際そうなんだろうけれども、問題のスケールが小さいから実務的にそう解けるというだけのことであって、なんか納得いかない感じが残った。
5桁の場合であっても総当たりしてgrepで条件文重ねて絞り込めば簡単に解けて150通りであることは分かる。
perl -e "@g=grep{$_!~/[04-9]/ and /1/ and /2/ and /3/}('11111'..'33333');print $_+1,qq/\t$g[$_]\n/ for 0..$#g;"
ただ自分は2進数でマスクを取る方法に期待があってそれについて考えていた。
3種の数字で4桁の場合はそれほど問題なくて3種の文字を1度ずつ使って作られる順列
123
132
213
231
312
321
と、重複位置が記された2ビットのマスク
1100
1010
1001
0101
0110
0011
の組み合わせが6×6通りというのは理解しやすい。
ただこの時の順列とマスクの演算方法をどうすればいいのかは懸念として残った。
（ここは前回冒頭の手順(3)に該当すると思う。）
最左桁同士から積を取っていき、マスクに1が立っていたら掛けられる数を記憶しておき、次にマスクビットが立った時にそれを挿入する…？みたいなことを考えていた。
しかしそうすると5桁にした際に演算法が複雑になる。
3種の数字をすべて使った5桁の数を作る場合、同様に重複位置を示すビット列の表現は、4桁のように2ビットのマスク1枚というわけにはいかない。
重複する数字が1個の場合は3ビットのマスク1枚(例：数11123に対しマスク11100)、あるいは排他的な2ビットマスクを2枚重ねる（例：12123に対しマスク10100,01010）となる。
前回自分は後者についての考えが至らず「5桁になったら3進数にするのか？」という発言につながった。
そう考えると5桁の場合についても順列×マスクパターンで場合の数を算出することができるはずで、マスクパターンは25通りとなることが予想できる。
3ビットの場合、以下の10通りであるのはすぐに分かる。
11100
11010
11001
10110
10011
10101
01110
01101
01011
00111
排他的な2ビットマスク2枚の場合、以下の30通り(!?)が考えられる。
11000,00110
11000,00101
11000,00011
10100,01010
10100,01001
10100,00011
10010,01100
10010,01001
10010,00101
10001,01100
10001,01010
10001,00110
01100,10010
01100,10001
01100,00011
01010,10100
01010,10001
01010,00101
01001,10100
01001,10010
01001,00110
00110,11000
00110,10001
00110,01001
00101,11000
00101,10010
00101,01010
00011,11000
00011,10100
00011,01100
今のままでは6×(10＋30)＝240通りとなってしまうので誤りであることが予想される。
マスクビットの左側を順列の再左桁の重複、マスクビットの右側を順列の中間桁の重複とすれば、
11223＝123×(11000,00110)＝213×(00110,11000)
となるのでマスクビットは半分の15通りとなり辻褄が合う。
（ここで×は一般的な積ではなくてさっき4桁の時に決めたなんかふわっとした演算の演算子）
一応場合の数について計算は合ったが、この3ビットと2ビット×2枚のマスクを扱いをまとめられないかと考えていた。
昨晩思いついたのが3桁の数と5桁の数をそれぞれ3次元ベクトルと5次元ベクトルとしてそれらの線形変換として表す方法で、その線形変換は3次元の正規直交基底を5本並べて作る行列とすれば統一的に表現できる。
具体的には、123という3桁の数と11100というマスクを11123という5桁の数に関連づけるにあたって、
(1 2 3)
という3次元ベクトルと
((1 1 1 0 0)
(0 0 0 1 0)
(0 0 0 0 1))
という3×5行列の積として
(1 1 1 2 3)
という5次元のベクトルを得る。
排他的な2ビットマスク2枚の場合も、例えば123と(10100,01010)から12123を得ることを、同様に
(1 2 3)
と
((1 0 1 0 0)
(0 1 0 1 0)
(0 0 0 0 1))
の積として
(1 2 1 2 3)
と表せる。
というわけで変換行列を使う方法を考えてみたものの、その変換行列を生成する方法や変換行列の性質についてまではまだわからない。
(1 2 3)
を
(1 3 2)
に変換する行列
((1 0 0)
(0 0 1)
(0 1 0))
は直交行列だが、今回求めた行列もなんか群を構成したりするんだろうか。
正方行列じゃないから逆行列定義できないけど一般化逆行列とかでその辺分かったりするのかな。
再帰 (スコア:0)
f(k) = 「丁度k種類の数字で5桁の数字を作る方法の数」
g(k) = 「k種類以下の数字で5桁の数字を作る方法の数」
とすると
f(3) = g(3) - (3C2)*f(2) - (3C1)*f(1)
(丁度3種で5桁を作る = (1〜3種で作る=g(3)) - (2種選んで(3C2)その2種だけで作る=3C2*f(2)) - (1種選んで(3C1)その1種だけで作る=3C1*f(1)))
同様に
f(2) = g(2) - (2C1)*f(1)
f(1) = g(1)
ここで g(k) = k^5 を用いて一番下の等式から埋めていけば f(1), f(2), f(3) が順に求まる。
f(1)=g(1)=1, f(2)=2^5-2*1=30, f(3)=3^5-3*30-3*1=150
ビットマスクも面白いですね!
Re:再帰 (スコア:1)
再帰も面白そうなんで、一般化した漸化式をちょっと考えてみました。
f(n,k) = 「丁度k種類の数字でn桁の数字を作る方法の数」
f(x,1) = 1 : 1種類の数字の場合は、何桁でも一通り
f(x,y) = 0 if (x y) : 桁数よりも種類数が多い場合は、実現不可能
n桁でちょうどk種類使うのは、以下の2パターンの和になる
n-1桁でk種類使ってる場合は、最後のn桁目はk種類の数字のどれを入れてもいい
→f(n-1),k) * k 通り
n-1桁でk-1種類使って、n桁目にに残った1種類を使う。最後の1桁は確定だが、その「残った1種類」はk通りある。
→f(n-1,k-1) * k 通り
以上を式にすると、
f(n,k) = f(n-1,k) * k + f(n-1,k-1) * k
これを元に再帰的計算すると、
3種類の数字で5桁の数字を作る方法の数 f(5,3) は、
まず再帰の下り
f(5,3) = f(4,3) * 3 + f(4,2) * 3
f(4,3) = f(3,3) * 3 + f(3,2) * 3
f(4,2) = f(3,2) * 2 + f(3,1) * 2
f(3,3) = f(2,3) * 3 + f(2,2) * 3
f(3,2) = f(2,2) * 2 + f(2,1) * 2
f(3,1) = 1
f(2,3) = 0
f(2,2) = f(1,2) * 2 + f(1,1) * 2
f(2,1) = 1
f(1,2) = 0
f(1,1) = 1
上り
f(2,2) = f(1,2) * 2 + f(1,1) * 2 = 2
f(3,2) = f(2,2) * 2 + f(2,1) * 2 = 2 * 2 + 1 * 2= 6
f(3,3) = f(2,3) * 3 + f(2,2) * 3 = 0 * 3 + 2 * 3 = 6
f(4,2) = f(3,2) * 2 + f(3,1) * 2 = 6 * 2 + 1 * 2 = 14
f(4,3) = f(3,3) * 3 + f(3,2) * 3 = 6 * 3 + 6 * 3 = 36
f(5,3) = f(4,3) * 3 + f(4,2) * 3 = 36 * 3 + 14 * 3 = 150
ってことで、150通りになる。
シンプルに定式化できたと思うんですが、
再帰を二回呼び出すから、実際に使うとフィボナッチ的で効率は悪そう。
Re: (スコア:0)
この方法を応用すると、カウントする代わりに組み合わせを作っていくこともできる。数列から条件に合うものをフィルタリングする方法が最もシンプルではあるが、1つずつ条件に合うものを探索していく方法よりは遥かにシンプル。そして、条件を変えるときも単に引数を変えるだけ。素晴らしい。
Re: (スコア:0)
f(k)をk!で割ると第2種スターリング数の公式に
https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Expl... [wikipedia.org]
置換行列 (スコア:0)
対称群の線形表現
Re:置換行列 (スコア:1)
重複を許したら置換ではなくなるから対称群にもならない気がする。
4桁の場合でも4種類の数字を使う場合24通りで、これを3種類に減らすと36通りに増えるということは群の要素が増えてることになるんじゃないのか。
二進数のマスクで考える (スコア:0)
＜1番目の数字が3回出現するパターン＞
(1) 1のところには1番目の数字、0のところには2番めの数字と3番めの数字が入る。以下の10通り。
(2) 2番目の数字と3番目の数字が入る場所は2つ。1のところに2番目の数字、0のところに3番目の数字が入る。ビット反転したものも含めて重複がないのは以下の1通り。
(3) したがって、決まった順序の数字の入れ方は10×1＝10通り。(A)
＜1番目の数字と2番目の数字が2回ずつ出現するパターン＞
(1) 1番目の数字と2番目の数字を区別せず、1のところには1番目の数字か2番目の数字が入るものとして考える。0のところに3番目の数字が入る。5通り。
（2）1番目の数字と2番目の数字が入る場所は4つ。1のところに1番目の数字、0のところに2番目の数字が入る。ビット反転したものも含めて重複がないのは以下の3通り。
(3) したがって、決まった順序の数字の入れ方は5×3=15通り。(B)
3つの数字の並べ方は6通りなので、((A)+(B))×6=(10+15)×6=150通り。