３６通り

８月８日水曜日、雨（復帰丗九日目）

台風１３号が近づいている。９日になった真夜中のいま、結構風が強くなっている。

さておき。

アンディ・ウィアー『アルテミス』を読んでいる。楽しい。おっぱい。女の子が主人公なのに、言わせちゃう。
知っている人は知っている映画『オデッセイ』の原作本『火星の人』の二作目。（原題は The Martian。火星は英語で Mars と s で終わるのに火星人は Martian と t に変わるのはなぜですか？　いじめ？　意地悪？）

ドキドキハラハラしながら下巻を読んでいるところです。

＊　＊　＊

ところで。
その下巻の最初に『ふーん。三つの数字で四桁のコードか。わたしは目を閉じて計算した。組み合わせは……五四通り』という場面が出てくる。（四桁の PIN コードを当てる。使われている数字が三つ、０と１と７だというところまでわかっている状況）

組み合わせ、数え上げに僕は苦手意識がある。だから主人公のジャスミンことジャズが目を閉じて、つまり暗算で（！）組み合わせを計算したというところに燃えるような嫉妬を覚えてしまった。（バカだよね。相手は小説の中の架空の人物。ひょっとすると作者が１週間紙と鉛筆で格闘して、その結果を書いているだけかもしれないというのに。わかってる。バカだ。僕は）

５４通りが正しいとして、これは２掛けることの３の３乗に因数分解できる。いったいどういう想定でこの数字が出てきたのか。
すごく気になる。

そして実際のところ、三つの数字が手元にあるとして。この三つで四桁の数をつくる場合、どういう考え方をしたら漏れなく、ダブりなく、すべての場合を尽くせるのだろう？

＊　＊　＊

ツイートしたとおり、僕は３６通りになるとおもっている。

＊　＊　＊

最初に考えた方法。

最初に三つの数字を並べて、あと一桁をいずれかから複製する。複製した数字を置く位置も考慮に入れる……。
つまり。

「０７１」と並べたとして、次の６通りの複製の仕方が考えられる。
Ａ）最初の０（０番目）を複製して右隣（１番目）に置く ── ００７１
Ｂ）最初の０（０番目）を複製して二つ隣（２番目）に置く ─ ０７０１
Ｃ）最初の０（０番目）を複製して右端（３番目）に置く ── ０７１０
Ｄ）真ん中の７（１番目）を複製して右隣（２番目）に置く ─ ０７７１
Ｅ）真ん中の７（１番目）を複製して右端（３番目）に置く ─ ０７１７
Ｆ）右端の１（２番目）を複製して隣（３番目）に置く ─── ０７１１
この複製で生成した数字列にダブりはない。

念のため０を頭に置くもう一つの並べ方を確認。０１７に対して６通りの複製法でダブりのない四桁が得られる。
００１７
０１０７
０１７０
０１１７
０１７１
０１７７
そしてそれぞれ最初の００７１と００１７は違っていて、残りは最初の二桁目が違うので、すべて違う並びができている。

さて、最初の数字の並べ方は３掛ける２で６通り（単純な組み合わせ）。

複製のタネになる６通りの数字の並びそれぞれに異なる６通りの複製の仕方がある。
つまり掛け算で３６通り。

＊　＊　＊

もうひとつ、考えてみた。

０、１、７のうち、どれか一つを複製する。例えば１を複製して手元に０、１、１、７の数字があることにして、これを並べ替えることを考える。

４つの異なる文字からできるすべての並べ方は順列（Permutation）として知られている。考え方は、最初は４つの好みの中から選べる。残りは３種類から２番目を選ぶ。残りは２種類、ここから３番目を選び、最後は選択肢なし。４掛ける３掛ける２（掛ける１）、答えは２４。

生成する順列の中に同じ文字が含まれている場合、それらは区別できないので取り除く必要がある。重複して数えた分を取り除けばよく、重なる文字数の階乗で順列を割った数になる。

今回の場合４文字のうち１種類の文字が二つ含まれているので「２！」、すなわち２で割ればよい。２４割る２で１２。

複製する数字は０、１、７の三つが選べるので１２を３倍して３６通り。

＊　＊　＊

ほんとに、ねえ。
どこから出てきたんだろう、５４？

＊　＊　＊

そしておもいだした。
僕はプログラマーだったのです。
飛び道具があった。

１０進数の四桁の数字は高々１万通り。
ここから０と１と７だけを含み、すべて使っているものを全部、コンピューターに数えさせてみよう。

えい！

[00] 0017
[01] 0071
[02] 0107
[03] 0117
[04] 0170
[05] 0171
[06] 0177
[07] 0701
[08] 0710
[09] 0711
[10] 0717
[11] 0771
[12] 1007
[13] 1017
[14] 1070
[15] 1071
[16] 1077
[17] 1107
[18] 1170
[19] 1700
[20] 1701
[21] 1707
[22] 1710
[23] 1770
[24] 7001
[25] 7010
[26] 7011
[27] 7017
[28] 7071
[29] 7100
[30] 7101
[31] 7107
[32] 7110
[33] 7170
[34] 7701
[35] 7710

疑いの余地なく３６通りでした。（でも頭悪い。気がする）

＊　＊　＊

使ったソースコード、載せておきますね。

/* artemis.c */
#include <stdio.h>
#include <memory.h>

typedef unsigned short number_t;

static void* filter(const void* begin, const void* end, unsigned size,
                    unsigned (*remove_if)(const void* elem, void* context),
                    void* context, void* result) {
 const char* p = begin;
 char *q = result;
 while (p != end) {
   if (!remove_if(p, context)) {
     memcpy(q, p, size);
     q += size;
   }
   p += size;
 }
 return q;
}

static unsigned not_three_figures(const void* elem, void *context) {
 const number_t* n = elem;
 number_t figure[10] = {0};
 number_t *it = figure;
 unsigned sum = 0;
 figure[(*n/1)%10] = 1;
 figure[(*n/10)%10] = 1;
 figure[(*n/100)%10] = 1;
 figure[(*n/1000)%10] = 1;
 while (it != figure + 10) {
   sum += *it;
   it += 1;
 }
 return sum != 3 || !(figure[0] && figure[1] && figure[7]);
}

int main() {
 number_t array[10000];
 number_t *it = array;
 number_t *end = array + 10000;

 /* initialize */
 while (it != end) {
   *it = (number_t)(it - array); /* distance */
   it += 1;
 }

 /* filter out, which does not fulfill condition */
 end = filter(array, end, sizeof(number_t), not_three_figures, NULL, array);

 /* print result */
 it = array;
 while (it != end) {
   printf("[%02ld] %04u\n", it - array, *it);
   it += 1;
 }

 return 0;
}

この C ソースコード artemis.c をコンパイルして実行すると、先の結果が得られます。開発ツールが入っている環境なら以下でおk。

make artemis && ./artemis