2020年6月3日水曜日

エクセルで順列

毎年,5個の順列が必要で,ずいぶんと前に作っていた。

たとえば,
a, b, c, d
の4個の順列は
abcd
abdc
acbd
.
.
.
dcba
の4!=24通りなので,その気になれば並べられるが,5個なら5!=120通り,6個なら6!=720通り
を手でミスなく列挙するのは大変。

で,機械の力を借りるのだが,エクセル作る方法。

もっといいやり方はないかとネットで調べると,VBA,つまりプログラムばかり出てくるが,べつにそんなことする必要ない。普通の表計算でできる。
泥臭いやり方だが,手で並べるよりは確実である。

まず,0,1,2,3 の4つで重複順列を作る。全部で 4^4=256個あるから,0から255まで番号を振って
0 0 0 0 0
1 0 0 0 1
2 0 0 0 2
3 0 0 0 3
4 0 0 1 0
5 0 0 1 1
6 0 0 1 2
7 0 0 1 3
8 0 0 2 0
.
.
.
255 3 3 3 3
これは0から255までの番号を4^3, 4^2, 4^1, 4^0 で割って mod 4 すれば並ぶ。
=MOD(INT(\$A2/4^3),4)

たとえば,
103÷4^3=103÷64=1.609375 の整数部 1≡1 (mod 4)
103÷4^2=103÷16=6.4375 の整数部 6≡2 (mod 4)
103÷4^1=103÷4=25.75 の整数部 25≡1 (mod 4)
103÷4^0=103÷1=103≡3 (mod 4)
より,
103 は 1 2 1 3
という重複順列になる。


この4つの数字の中に,同じ数字が何個あるか数える。countifで
1 が 2 個
2 が 1 個
1 が 2 個
3 が 1 個
より,
103 1 2 1 3  2 1 2 1 (1が2個,2が1個,1が2個,3が1個)
この 1 2 2 1 の最大値を求め, 1 に等しいか判定。
=MAX(F106:I106)=1
1に等しければ(TRUE) で,4つの数字が全部異なるから,順列である。

true ならすべて異なる数だから順列で,先頭からそこまでの trueの個数を数える。これが順列の番号になる。
=IF(J106,COUNTIF(J\$2:J106,TRUE),".")で先頭からのtrueの個数 COUNTIF(J\$2:J106,TRUE) を表示。
そして,true なら,4つの数字を並べる。
108 1 2 3 0 1 1 1 1 TRUE 10 1 2 3 0
順列の10番目は 1 2 3 0

false なら同じ数字を含むので順列ではないから,数えない。
=IF(J106,COUNTIF(J$$2:J106,TRUE),".")で "." 表示。
103 1 2 1 3  2 1 2 1 FALSE . . . . .

true であるものは
1 2 3 0 を対応表で, b c d a と変換して,文字列の連結で bcda という順列にする。
順列の10番目は bcda

対応表
0 a
1 b
2 c
3 d

そして,順列の番号 1から 24 に対して,連結した文字列を vlookup で拾って
1 abcd
2 abdc
3 acbd
4 acdb
.
.
.
23 dcab
24 dcba
にまとめれば完成。

問題点は重複順列すべて並べてから,同じ数字をもつものをはじくところ。
重複順列をすべて並べるには
5文字なら,5!=120通りの生成のために26倍の 5^5=3125行,
6文字なら,6!=720通りの生成のために65倍の 6^6=46656行,
7文字なら,7!=5040通りの生成のために163倍の 7^7=823543行
必要になる。エクセルの約100万行なら,これが1枚のシートでできる最大。

もっといい方法がありそう。ただし,プログラム(VBA)を使わずに。

0 件のコメント:

コメントを投稿

「コメントの記入者:」は「匿名」ではなく,「名前/URL」を選んで,なにかニックネームを入れてください.URL は空欄で構いません.