プログラミング初学者向けの内容です。
今のところ Golang, Ruby, Python, JavaScript, TypeScript, Rust, VBA による処方箋のみ掲載しています。
- 2020 年 10 月 3 日 追記（アルゴリズムについて）
- 2020 年 10 月 5 日 追記（Rust で調合する)
- 2020 年 10 月 5 日 追記（VBA で調合する)
ある日のこと
知人「店長からさぁ、
『うちはメニューの数が少ないから、
コンビ・メニュー作ることにした』
『とりあえず、
今あるメニューを組み合わせて、
単品から全部入りまで
すべての組み合わせのリスト作ってくれ！』
って、言われたんだけど…」
俺「え？ それって、
🍔🍟🥤があるとしたら、
↓みたいなやつ？」
1:🍔
2:🍟
3:🍔 🍟
4:🥤
5:🍔 🥤
6:🍟 🥤
7:🍔 🍟 🥤
知人「そう。そう。それ！それ！」
俺「作れるけど、、
きっとものすごい数になるよ。
単品メニューって何種類くらいあんの？」
知人「20種類くらいかなぁ。。
物好きな店長でしょ？！
めんどくせぇ。。」
俺「…」
俺「あのさぁ、、
面倒くさいとかの次元じゃないんだけど。。」
俺「0.1 mm 厚の紙を 26 回折ったら
富士山より高くなるって知ってる？」
\begin{align}
0.1 \, \mathrm{mm}\times2^{26} &= 6,710,886.4 \, \mathrm{mm}\\
&\fallingdotseq 6.7 \, \mathrm{km}
\end{align}
知人「あ、なんか聞いたことあるかも。。」
俺「それと同じなんだけど、、」
\begin{align}
2^{20} - 1 &= 1,048,575 通り\\
&\fallingdotseq 105万通り
\end{align}
俺「105万通りは、
さすがにメニュー充実しすぎだろ（笑）」
知人「へ〜、そんなになるんだぁ！」
俺「…」
Golang による処方箋
取り急ぎ Golang で書いてみます。
package main
import (
"flag"
"fmt"
"strings"
)
func comball(in []string) [][]string {
n := 1 << len(in)
out := make([][]string, n)
for i := 0; i < n; i++ {
ss := make([]string, 0, len(in))
for j := 0; j < len(in); j++ {
if 1<<j&i != 0 {
ss = append(ss, in[j])
}
}
out[i] = ss
}
return out
}
func main() {
flag.Parse()
args := flag.Args()
for i, ss := range comball(args) {
fmt.Printf("%d:%s\n", i, strings.Join(ss, " "))
}
}
Go のバージョンです。
$ go version
go version go1.15.2 linux/amd64
実行してみます。
$ go run menu.go 🍔 🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛 > menu.txt
Golang はコンパイルも実行も速くていいですね。
Generics をサポートしていないので string 型専用の関数になってしまい、そこが残念ポイントですが、LL のような感覚で気軽にいろいろ試せます。
（Generics は来年サポートされるようですね）
プログラムは標準出力へ書き出すようにしましたが、そのまま出力するとたぶん大変なことになるので menu.txt という名前のファイルへリダイレクトしました。
ファイルの先頭を見てみます。
$ head menu.txt
0:
1:🍔
2:🍟
3:🍔 🍟
4:🥤
5:🍔 🥤
6:🍟 🥤
7:🍔 🍟 🥤
8:🍮
9:🍔 🍮
最初の行に「なし」を出すようにしてます。
今度は末尾を見てみます。
$ tail menu.txt
1048566:🍟 🥤 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048567:🍔 🍟 🥤 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048568:🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048569:🍔 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048570:🍟 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048571:🍔 🍟 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048572:🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048573:🍔 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048574:🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048575:🍔 🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1行目の「なし」を除いて、ちゃんと 104 万 8,575 行あります。
ファイルサイズが 56.4 MiB もありますが、、（笑）
（圧縮して 4 Mib くらい）
ひとまず、これで大丈夫そうです。
あと、 Golang はサクッとクロスコンパイルしてシングルバイナリが作れるのがいいですね！
とりあえず、AMD64 互換 の linux と Mac と Windows 用を用意して持ち帰ってもらうことにました。
GOOS=linux GOARCH=amd64 go build -o ./linux-amd64/menu menu.go
GOOS=darwin GOARCH=amd64 go build -o ./darwin-amd64/menu menu.go
GOOS=windows GOARCH=amd64 go build -o ./windows-amd64/menu.exe menu.go
でも、、
せっかくプログラムを書いてあげたのに、結局、彼は「店長に怒られそう…」という理由で、これを使ってくれませんでした。
遠い昔を思い出す
知人は採用してくれませんでしたが、これってテストデータの生成（フラグの組み合わせとか）にも応用できますよ。
昔、入社 1 年目のとき、まるで野球部の球拾いのごとくテスターをやらされた日々を思い出します。
ある日、明確なテスト仕様書もない中で、先輩 SE から無茶振りされました。
「可能な組み合わせを全部テストするなんて当たり前なの！お前バカなの！？」
と怒鳴られました。
遠い昔のことなので、細かいことはあまり良く覚えてませんが、同期の仲間と計算してみると、1 個 1 分でやったとしても、寝ずにやって何十年かかるとか、そんな途方もないオーダーでした。
現実的な解が思い浮かばなかったので、もっと上の先輩に相談しました。
すると、即答で「バカは相手にしなくていいから（笑）！」と言ってくれ、あっさりとこの問題は解決してしまいました。
今考えると完全にパワハラでした。
2〜3日、真剣に悩みましたから（笑）
無茶ぶりした先輩 SE はその後しばらくして会社を辞めていきました。
でも、マシンが高速化し自動テストがあたりまえになった現代では、当時できなかったいろんなことができるようになりました。
あのとき、もし今の環境が手元にあったら、この程度の簡単な処方箋であっさりと解決していたのかも。。
そう考えると感慨深いものがあります。
先輩 SE が後輩を馬鹿呼ばわりすることもなく、彼がさらに上の先輩から馬鹿呼ばわりされることもなかったかもしれません。
ということで、他の言語の例もいくつか載せておきます。
Ruby で調合する
Ruby はあまり書いたことがないので、らしいコードじゃないかもしれません。
プログラムをみる
def comb(arr)
out = []
n = 1 << arr.size
n.times do |i|
a = []
arr.size.times do |j|
if 1 << j & i != 0
a << arr[j]
end
end
out << a
end
out
end
comb(ARGV).each.with_index(0) do |a, i|
puts i.to_s + ":" + a.join(" ")
end
$ ruby --version
ruby 2.7.0p0 (2019-12-25 revision 647ee6f091) [x86_64-linux]
$ ruby menu.rb 🍔 🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛 > menu.txt
$ tail menu.txt
1048566:🍟 🥤 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048567:🍔 🍟 🥤 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048568:🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048569:🍔 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048570:🍟 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048571:🍔 🍟 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048572:🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048573:🍔 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048574:🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048575:🍔 🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
まあ、Ruby の場合は組み込み関数を使えば、↓これでもいけますね。
出力順が違いますけど。。
def comball(arr)
out = [[]]
arr.each_with_index { |s, i| out += arr.combination(i+1).to_a }
out
end
comball(ARGV).each.with_index(0) do |a, i|
puts i.to_s + ":" + a.join(" ")
end
Ruby って、書く順番がなんか他の言語と違いますよね。
この感覚が気持ちよくて好きです。。
Python で調合する
プログラムをみる
import sys
def comball(arr):
out = []
n = 1 << len(arr)
for i in range(n):
a = []
for j in range(len(arr)):
if 1 << j & i != 0:
a.append(arr[j])
out.append(a)
return out
arr = sys.argv
arr.pop(0)
for i, a in enumerate(comball(arr)):
s = ' '.join(a)
print('{0}:{1}'.format(i, s))
$ python3 --version
Python 3.6.8
$ python3 menu.py 🍔 🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛 > menu.txt
$ tail menu.txt
1048566:🍟 🥤 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048567:🍔 🍟 🥤 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048568:🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048569:🍔 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048570:🍟 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048571:🍔 🍟 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048572:🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048573:🍔 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048574:🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048575:🍔 🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
end や } が必要ない分、関数本体が短く書けますね。
JavaScript で調合する
プログラムをみる
function comball(arr) {
const out = []
const n = 1 << arr.length
for (let i = 0; i < n; i++) {
const a = []
for (let j = 0; j < arr.length; j++) {
if ((1 << j & i) != 0) {
a.push(arr[j])
}
}
out.push(a)
}
return out
}
const arr = process.argv.slice(2)
comball(arr).forEach((a, i) =>
console.log(i + ":" + a.join(" "))
)
$ node --version
v12.16.1
$ node menu.js 🍔 🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛 > menu.txt
$ tail menu.txt
1048566:🍟 🥤 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048567:🍔 🍟 🥤 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048568:🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048569:🍔 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048570:🍟 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048571:🍔 🍟 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048572:🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048573:🍔 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048574:🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048575:🍔 🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
JavaScript って & より != の方が演算子の優先順位が高いんですよね。
だから括弧が付いてます。
なんか理由があるんですかね。。
TypeScript で調合する
プログラムをみる
function comball<T>(arr: T[]): T[][] {
const out: T[][] = []
const n = 1 << arr.length
for (let i = 0; i < n; i++) {
const a: T[] = []
for (let j = 0; j < arr.length; j++) {
if ((1 << j & i) != 0) {
a.push(arr[j])
}
}
out.push(a)
}
return out
}
const arr: string[] = process.argv.slice(2)
comball(arr).forEach((a, i) =>
console.log(i + ":" + a.join(" "))
)
$ npx ts-node --version
v8.10.1
$ npx ts-node menu.ts 🍔 🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛 > menu.txt
$ tail menu.txt
1048566:🍟 🥤 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048567:🍔 🍟 🥤 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048568:🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048569:🍔 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048570:🍟 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048571:🍔 🍟 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048572:🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048573:🍔 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048574:🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048575:🍔 🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
TypeScript は関数シグネチャを見れば何をしそうか分かるところが良いですね。
あと、Generics 使っています。
でも、トランスパイルが遅いところが玉に瑕です。
Rust で調合する
(2020 年 10 月 5 日追記)
YoshiTheChinchilla さんから、Rust の filter_map() を使った実装を教えてもらったので、その方法で記します。
また、YoshiTheChinchilla さんからは、「店長から『なし』を含めるという要求はなかった」というコメントをもらい、「なるほど確かに！」と納得してしまいました（笑）
ただ、他のプログラムも先頭行に 0 として「なし」を出力しているので、以下はそれに合わせた実装としています。
プログラムをみる
提案してもらったものと実装を少し変えてるので、このプログラムが変だなと思った方は、コメント欄の YoshiTheChinchilla さんのオリジナルの方をご覧くださいね。
use std::env;
fn comball<T: Copy>(a: Vec<T>) -> Vec<Vec<T>> {
let n = a.len();
(0..1<<n).map(|i| {
(0..n).filter_map(|j| {
if 1 << j & i != 0 {
Some(a[j])
} else {
None
}
}).collect()
}).collect()
}
fn main() {
let mut argv: Vec<String> = env::args().collect();
argv.remove(0);
let argv = argv.iter().map(AsRef::as_ref).collect();
for (i, a) in comball(argv).iter().enumerate() {
println!("{}:{}", i, a.join(" "))
}
}
$ cargo --version
cargo 1.46.0 (149022b1d 2020-07-17)
$ cargo run 🍔 🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛 > menu.txt
$ tail menu.txt
1048566:🍟 🥤 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048567:🍔 🍟 🥤 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048568:🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048569:🍔 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048570:🍟 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048571:🍔 🍟 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048572:🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048573:🍔 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048574:🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
1048575:🍔 🍟 🥤 🍮 🥨 🌮 🍲 🍙 🍛 🍜 🍝 🍣 🍡 🍦 🍧 🍨 🍩 🍪 ☕ 🥛
Some() と評価したものだけ result に含めてくれる filter_map()、すごく好きです。
（Ruby でも同じような書き方ができそうですね）
書き慣れてないというのが大きいですが、Rust はいろいろな書き方ができるので、なかなかスムーズに書けません。String と &str の使い分け、Vec の使いこなし、他にもトレイト境界の使いこなし、ジェネリックなライフタイムパラメータの取り扱いなど、もっともっとコードを書いて慣れないとダメですね。
VBA で調合する
(2020 年 10 月 5 日追記)
Rust をやったら（といってもほとんど他人の肩の上に乗せてもらってますが）、他の言語でも実装してみたくなりました。
ということで Rust とは真逆の立ち位置の VBA で実装してみました。
プログラムをみる
Option Explicit
Sub clear()
Range(Cells(2, 1), Cells(2, 1).End(xlDown).End(xlToRight)).clear
End Sub
Function comball(arr As Variant) As Variant
Dim n As Long
n = 2 ^ (UBound(arr) - LBound(arr) + 1)
Dim out As Variant
out = Array()
Dim i As Long
For i = 0 To n - 1
Dim a As Variant
a = Array()
Dim j As Integer
For j = LBound(arr) To UBound(arr)
If (2 ^ (j - LBound(arr)) And i) <> 0 Then
ReDim Preserve a(UBound(a) - LBound(a) + 1)
a(UBound(a)) = arr(j)
End If
Next
ReDim Preserve out(UBound(out) + 1)
out(UBound(out)) = a
Next
comball = out
End Function
Sub menu()
Dim a As Variant
a = Range(Cells(1, 2), Cells(1, 2).End(xlToRight)).Resize(2).Value
a = WorksheetFunction.Index(a, 1)
Dim aa() As Variant
aa = comball(a)
Application.ScreenUpdating = False
On Error GoTo Finally
Dim i As Long
For i = LBound(aa) + 1 To UBound(aa)
a = aa(i)
Cells(i + 1, 1).Value = i
Dim j As Integer
For j = LBound(a) To UBound(a)
Cells(i + 1, j + 2).Value = a(j)
Next
Next
Finally:
Application.ScreenUpdating = True
End Sub
実行結果
セル A1 の cls ボタンを clear() へ、menu ボタンを menu() へ紐づけています。
あと、Excel の行数の最大値って 1,048,576 行なんですね。
1行目を入力パラメータ用に使っているので、先頭行の「0: なし」を出力しないようにして、最大行数ぴったりに収まるようにしました。
いやあ、VBA での実装が一番難しかったです。
（単に書き慣れてないだけかもしれませんが。。）
以下のポイントで躓きました。
- シフト演算子がない。2 のべき乗で代用。
- 配列インデックスの最小値がコンテキストにより異なる(0 だったり 1 だったりする)
- Integer が 16 ビット。32,768 でオーバーフロー。
- Variant 型の 2 次元動的配列
- 配列とシート間のデータ交換
あと、上記コードでは実行に 7 分もかかってしまいます。
(Glang で 3 〜 4 秒、Rust で 6 〜 7 秒でした)
VBA 猛者の方、もっと良い書き方を教えてください！
アルゴリズムについて
(2020 年 10 月 3 日追記)
投稿後の standard-software さんとのやり取りで、もしかしたら本稿に掲載したプログラムは書いた本人以外には読みにくいのかもしれないと思い至るようになりました。
ベテランの方が読みづらいと感じたのであれば、初学者の方は尚更分かりにくいはずです。
ということで、アルゴリズムについて簡単に説明しておきますね。
（standard-software さん、気付きを与えてくれてありがとうございます）
本稿では同じ機能を持つプログラムを複数の言語で書いていますが、データ構造とアルゴリズムはどれも同じです。
二分木 (Binary tree)
まずデータ構造ですが、今回のような組み合わせの問題は「二分木」という構造で表現することができます。
例として 🍔 🍟 🥤 🍮 の 4 アイテムの組み合わせを二分木で表現したのが以下の図になります。
上図は、最初に 🍔 の「あり」「なし」があって、
🍔 の「あり」の下に、🍟 の「あり」「なし」、
🍔 の「なし」の下にも🍟 の「あり」「なし」、
🍟 の …
という具合に枝が増えていきます。
性格診断の「YES/NO 選択チャート」なども同じような構造をしてますよね！？
さて、この木構造をプログラムでどう表現したら良いでしょうか。
下図は木を横にし、🍮 をトップに、🍔 が枝先になるようにアイテムの並び順を逆にしたものです。
このように木の向きを変えると、このツリー構造がそのまま 4 ビット幅の 2 進数で表現できることが分かるのではないでしょうか？
「無無無🍔」は 2 進数で 0001、
「🍮🥤無無」は 2 進数で 1100 です。
そうです。
🍮🥤🍟🍔 のすべての組み合わせは、2 進数の 0000 〜 1111 で表すことができるんです。
ここまで来れば、データ構造のイメージがかなり掴めたのではないでしょうか。
そして、2 進表現ではアイテムの on/off を示すフラグ配列のように見えますが、
0000 〜 1111 は、10 進表現で表すと普通の 0 〜 15 の数値ですよね。
つまり、これを整数型の変数に代入して、++ などでインクリメントしていけば、0000 〜 1111 のすべての状態を for ループで数え上げることができるんです。
ビット演算
あとはプログラムで 0000 〜 1111 の数値を、🍮🥤🍟🍔を組み合わせた配列に変換するだけです。
具体的には、
0001 なら 配列[🍔] へ、
0011 なら 配列[🍔,🥤] へ、
1111 なら 配列[🍔,🍟,🥤,🍮] へ変換するのですが、
(数値の並びとアイテムの並びが逆になっていることに注意してください)
これをシンプルに行うために、本稿のプログラムではビット演算を使っています。
忘れてしまっている人もいるかもしれないので、念のためにプログラム内で使われている演算子について簡単に説明しておきますね。
| 演算子 | 意味 | 例 |
|---|---|---|
| << | ビット左シフト 左辺の数値のビット列を、 右辺の数だけ左へずらす。 右側は 0 で埋める。 |
0b0111 **<<** **1** => 0b**1110** 0b**0001** **<<** **3** => 0b1000 |
| & | ビット論理積 (AND) 右辺と左辺の数値をビットごとに比較し、 両方とも1の桁を1に、それ以外を0にする。 |
0b0001 & 0b1111 => 0b0001 0b0101 & 0b1010 => 0b0000 |
なお、2 進数、シフト演算、論理積について曖昧なままにしている人も多いかもしれませんが、これって 「IPA 基本情報技術者試験 シラバス」 の1丁目1番地に登場する項目なんです。
忘れてしまった人は一度見直しておくといいかもしれません。
(IPA 基本情報技術者試験 シラバス より引用)
大分類 1: 基礎理論 - 中分類 1: 基礎理論
- 離散数学
（1）基数
2 進数，8 進数，10 進数，16 進数，n 進数の表現，2 進数と 10 進数などの基数の変換手法を理解する。
(中略)
（3）算術演算と精度
加減乗除，表現可能な数値の範囲，シフト演算，演算精度（誤差とその対策）など，コンピュータにおける算術演算を理解する。
(中略)
（5）論理演算
論理式の表現，論理演算，ド・モルガンの法則などの基本法則，真理値表の手法を理解する。
プログラムの説明
さて、データ構造とビット演算について整理したところで、改めてプログラムを見てみましょう。
以下は前述の JavaScript のプログラムにコメントを付けたものです。
(引数に 🍔🍟🥤🍮 の 4 アイテムが渡された想定のコメントになっています)
function comball(arr) { // arr は [🍔, 🍟, 🥤, 🍮] の 4 アイテム
const out = [] // 戻り値 out は 2 次元配列
const n = 1 << arr.length // 0001 を 左へ 4 桁シフトすると 10000 (16)
// i は単なるカウンタではなく、すべての組み合わせを表現するデータ
// i => 0000 〜 1111 でループ (0 〜 15)
// 0: 0000 1: 0001 2: 0010 3: 0011 ... 15: 1111
// 無無無無、無無無🍔、無無🍟無、無無🍟🍔、...、🍮🥤🍟🍔
for (let i = 0; i < n; i++) {
const a = []
// j => 0 〜 3 でループ
// 0🍔, 1🍟, 2🥤, 3🍮
for (let j = 0; j < arr.length; j++) {
// j は単なるカウンタではなく、アイテムを示すデータ
// 1 を j だけ左シフトすると、i (組み合わせデータ)とアイテムの桁位置が一致する
// j 1 << j & (i: 0000 i: 0001 i: 0010 ... i: 1111)
// 0🍔 => 無無無🍔 & (無無無無、無無無🍔、無無🍟無、...、🍮🥤🍟🍔)
// 1🍟 => 無無🍟無 & (無無無無、無無無🍔、無無🍟無、...、🍮🥤🍟🍔)
// 2🥤 => 無🥤無無 & (無無無無、無無無🍔、無無🍟無、...、🍮🥤🍟🍔)
// 3🍮 => 🍮無無無 & (無無無無、無無無🍔、無無🍟無、...、🍮🥤🍟🍔)
if ((1 << j & i) != 0) {
a.push(arr[j]) // 組み合わせ i に アイテム j が含まれていれば配列に追加
}
}
// 0000 0001 0010 0011 0100 1111
// out は [ [ ], [🍔], [🍟], [🍔🍟], [🥤], ..., [🍔🍟🥤🍮] ]
out.push(a)
}
return out
}
どうですか？
大夫理解できるようになったのではないでしょうか。
あとがき
本稿で扱ったプログラミング言語は演算子の使い方もほとんど同じなので、みんな似たコードになりましたが、それでも各言語の個性が出ている部分もあって面白かったです。
(2020 年 10 月 5 日追記)
Rust と VBA の実装は他とは少し雰囲気が違いました。
気が向けば、また他の言語での実装も追記するかもしれません。
あと、各言語のエキスパートの方で、もっとカッコいい書き方を知ってるよ！ という人は是非教えてください。
それでは！