JavaScript Junk Scripts

順列と組み合わせ

●仕様 (ジェネレータ版)

ファイル名: combination.js
iota(s, n, step=1) => array
数列の生成、s から始まり step 刻みの数を n 個配列に格納して返す
bag_of(gen) => array
ジェネレータ gen が生成する要素を配列に格納して返す
factorial(n) => BigInt
n の階乗 (n!) を求める
permutation_number(n, r) => BigInt
n 個の中から r 個を選ぶ順列の総数を求める
permutation(n, xs) => gen
配列 xs から n 個の要素を選ぶ順列を生成するジェネレータを返す
permutation_with_repetition(n, xs) => gen
配列 xs から n 個の要素を選ぶ重複順列を生成するジェネレータを返す
combination_number(n, r) => BigInt
組み合わせの数 _nＣ_r を求める
combination(n, xs) => gen
配列 xs から n 個の要素を選ぶ組み合わせを生成するジェネレータを返す
combination_with_repetition(n, xs) => gen
配列 xs から n 個の要素を選ぶ重複組み合わせを生成するジェネレータを返す
derangement(m) => gen
m 個の数 [0 .. m-1] の完全順列を生成するジェネレータを返す
montmort_number(n) => BigInt
モンモール数 (完全順列の総数) を求める
product(xs, ys, ...) => array
配列 xs, ys, ... の直積集合を生成するジェネレータを返す
ライセンス: MIT

●プログラムリスト

//
// combination.js : 順列と組み合わせ
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//

// 数列の生成
function iota(s, n, step = 1) {
    let buff = new Array(n);
    for (let i = 0; i < n; i++) {
        buff[i] = s;
        s += step;
    }
    return buff;
}

// ジェネレータの要素を配列に格納して返す
function bag_of(gen) {
    let bag = [];
    for (let x of gen) bag.push(x);
    return bag;
}

// 階乗
function factorial(n) {
    let a = 1n;
    while (n > 0) a *= BigInt(n--);
    return a;
}

// n 個の中から r 個を選ぶ順列
function permutation_number(n, r) {
    let a = 1n;
    while (r-- > 0) a *= BigInt(n--);
    return a;
}

// 順列の生成
function* permutation(n, xs, ps = [], flag = new Set()) {
    if (n == 0) {
        yield [...ps];
    } else {
        for (let x of xs) {
            if (!flag.has(x)) {
                flag.add(x);
                ps.push(x);
                yield* permutation(n - 1, xs, ps, flag);
                ps.pop();
                flag.delete(x);
            }
        }
    }
}

// 重複順列
function* permutation_with_repetition(n, xs, ps = []) {
    if (n == 0) {
        yield [...ps];
    } else {
        for (let x of xs) {
            ps.push(x);
            yield* permutation_with_repetition(n - 1, xs, ps);
            ps.pop();
        }
    }
}

// 組み合わせの数
function combination_number(n, r) {
    return permutation_number(n, r) / factorial(r);
}

// 組み合わせの生成
function* combination(n, xs, ys = [], i = 0) {
    if (n == ys.length) {
        yield [...ys];
    } else if (xs.length - i >= n - ys.length) {
        ys.push(xs[i]);
        yield* combination(n, xs, ys, i + 1);
        ys.pop();
        yield* combination(n, xs, ys, i + 1);
    }
}

// 重複組み合わせ
function* combination_with_repetition(n, xs, ys = [], i = 0) {
    if (n == ys.length) {
        yield [...ys];
    } else if (xs.length > i) {
        ys.push(xs[i]);
        yield* combination_with_repetition(n, xs, ys, i);
        ys.pop();
        yield* combination_with_repetition(n, xs, ys, i + 1);
    }
}

// 完全順列
// (0 .. m-1) の中から m 個を選ぶ
function* derangement(m, ps = [], flag = new Set()) {
    if (ps.length == m) {
        yield [...ps];
    } else {
        for (let x = 0; x < m; x++) {
            if (x != ps.length && !flag.has(x)) {
                flag.add(x);
                ps.push(x);
                yield* derangement(m, ps, flag);
                ps.pop();
                flag.delete(x);
            }
        }
    }
}

// モンモール数
function montmort_number(n) {
    let a = 0n, b = 1n;
    for (let i = 1; i < n; i++) [a, b] = [b, BigInt(i + 1) * (a + b)]
    return a;
}

// 直積集合
function* product_sub(xs, i = 0, a = []) {
    if (i == xs.length) {
        yield [...a];
    } else {
        for (let x of xs[i]) {
            a.push(x);
            yield* product_sub(xs, i + 1, a);
            a.pop();
        }
    }
}

function* product(...args) {
    yield* product_sub(args);
}

export {
    iota, bag_of, factorial, permutation_number, permutation,
    combination_number, combination, derangement, montmort_number,
    product, permutation_with_repetition, combination_with_repetition
}

●簡単なテスト

//
// test_combination.js : 順列と組み合わせのテスト
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
import * as M from './combination.js';
console.log("---- iota ----");
console.log(M.iota(0, 4));           // [0,1,2,3]
console.log(M.iota(0, 4, 2));        // [0,2,4,6]
console.log(M.iota(10n, 4, 1n));     // [10n, 11n, 12n, 13n,]
console.log(M.iota(10n, 4, -1n));    // [10n, 9n, 8n, 7n,]

console.log("---- factorial ----");
console.log(M.factorial(0));   // 1n
console.log(M.factorial(9));   // 362880n
console.log(M.factorial(10));  // 3628800n
console.log(M.factorial(15));  // 1307674368000n

console.log("---- permutation_number ----");
console.log(M.permutation_number(6, 1))   // 6
console.log(M.permutation_number(6, 3))   // 120
console.log(M.permutation_number(6, 6))   // 720
console.log(M.permutation_number(10, 4))  // 5040

console.log("---- permutation ----");
console.log(M.bag_of(M.permutation(2, [1,2,3])));
console.log(M.bag_of(M.permutation(3, [1,2,3])));
console.log(M.bag_of(M.permutation_with_repetition(2, [1,2])));
console.log(M.bag_of(M.permutation_with_repetition(2, [1,2,3])));

console.log("---- combination_number ----");
console.log(M.combination_number(5, 5))     // 1
console.log(M.combination_number(5, 3))     // 10
console.log(M.combination_number(5, 1))     // 5
console.log(M.combination_number(60, 30))   // 118264581564861424n

console.log("---- combination ----");
console.log(M.bag_of(M.combination(1, [1,2,3,4,5])));
console.log(M.bag_of(M.combination(3, [1,2,3,4,5])));
console.log(M.bag_of(M.combination(5, [1,2,3,4,5])));
console.log(M.bag_of(M.combination_with_repetition(2, [1,2])));
console.log(M.bag_of(M.combination_with_repetition(2, [1,2,3])));

console.log("---- montmort_number ----");
console.log(M.montmort_number(3))     // 2
console.log(M.montmort_number(4))     // 9
console.log(M.montmort_number(5))     // 44
console.log(M.montmort_number(20))    // 895014631192902121n

console.log("---- derangement ----");
console.log(M.bag_of(M.derangement(2)));
console.log(M.bag_of(M.derangement(3)));
console.log(M.bag_of(M.derangement(4)));

console.log("---- product ----");
console.log(M.bag_of(M.product([1,2,3,4])));
console.log(M.bag_of(M.product([1,2],[3,4])));
console.log(M.bag_of(M.product([1,2],[3,4,5])));
console.log(M.bag_of(M.product([1,2],[3,4],[5,6])));

●実行結果

$ node test_combination.js
---- iota ----
[ 0, 1, 2, 3 ]
[ 0, 2, 4, 6 ]
[ 10n, 11n, 12n, 13n ]
[ 10n, 9n, 8n, 7n ]
---- factorial ----
1n
362880n
3628800n
1307674368000n
---- permutation_number ----
6n
120n
720n
5040n
---- permutation ----
[ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]
[
  [ 1, 2, 3 ],
  [ 1, 3, 2 ],
  [ 2, 1, 3 ],
  [ 2, 3, 1 ],
  [ 3, 1, 2 ],
  [ 3, 2, 1 ]
]
[ [ 1, 1 ], [ 1, 2 ], [ 2, 1 ], [ 2, 2 ] ]
[
  [ 1, 1 ], [ 1, 2 ],
  [ 1, 3 ], [ 2, 1 ],
  [ 2, 2 ], [ 2, 3 ],
  [ 3, 1 ], [ 3, 2 ],
  [ 3, 3 ]
]
---- combination_number ----
1n
10n
5n
118264581564861424n
---- combination ----
[ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ]
[
  [ 1, 2, 3 ], [ 1, 2, 4 ],
  [ 1, 2, 5 ], [ 1, 3, 4 ],
  [ 1, 3, 5 ], [ 1, 4, 5 ],
  [ 2, 3, 4 ], [ 2, 3, 5 ],
  [ 2, 4, 5 ], [ 3, 4, 5 ]
]
[ [ 1, 2, 3, 4, 5 ] ]
[ [ 1, 1 ], [ 1, 2 ], [ 2, 2 ] ]
[ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 2 ], [ 2, 3 ], [ 3, 3 ] ]
---- montmort_number ----
2n
9n
44n
895014631192902121n
---- derangement ----
[ [ 1, 0 ] ]
[ [ 1, 2, 0 ], [ 2, 0, 1 ] ]
[
  [ 1, 0, 3, 2 ],
  [ 1, 2, 3, 0 ],
  [ 1, 3, 0, 2 ],
  [ 2, 0, 3, 1 ],
  [ 2, 3, 0, 1 ],
  [ 2, 3, 1, 0 ],
  [ 3, 0, 1, 2 ],
  [ 3, 2, 0, 1 ],
  [ 3, 2, 1, 0 ]
]
---- product ----
[ [ 1 ], [ 2 ], [ 3 ], [ 4 ] ]
[ [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ] ]
[ [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ] ]
[
  [ 1, 3, 5 ],
  [ 1, 3, 6 ],
  [ 1, 4, 5 ],
  [ 1, 4, 6 ],
  [ 2, 3, 5 ],
  [ 2, 3, 6 ],
  [ 2, 4, 5 ],
  [ 2, 4, 6 ]
]

●高階関数版

//
// comb_func.js : 順列と組み合わせ (高階関数版)
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//

// 数列の生成
function iota(s, n, step = 1) {
    let buff = new Array(n);
    for (let i = 0; i < n; i++) {
        buff[i] = s;
        s += step;
    }
    return buff;
}

// 要素を配列に格納して返す
function bag_of(func, ...args) {
    let bag = [];
    func(xs => bag.push(xs), ...args);
    return bag;
}

// 階乗
function factorial(n) {
    let a = 1n;
    while (n > 0) a *= BigInt(n--);
    return a;
}

// n 個の中から r 個を選ぶ順列
function permutation_number(n, r) {
    let a = 1n;
    while (r-- > 0) a *= BigInt(n--);
    return a;
}

// 順列の生成
function permutation(fn, n, xs, ps = [], flag = new Set()) {
    if (n == 0) {
        fn([...ps]);
    } else {
        for (let x of xs) {
            if (!flag.has(x)) {
                flag.add(x);
                ps.push(x);
                permutation(fn, n - 1, xs, ps, flag);
                ps.pop();
                flag.delete(x);
            }
        }
    }
}

// 重複順列
function permutation_with_repetition(fn, n, xs, ps = []) {
    if (n == 0) {
        fn([...ps]);
    } else {
        for (let x of xs) {
            ps.push(x);
            permutation_with_repetition(fn, n - 1, xs, ps);
            ps.pop();
        }
    }
}

// 組み合わせの数
function combination_number(n, r) {
    return permutation_number(n, r) / factorial(r);
}

// 組み合わせの生成
function combination(fn, n, xs, ys = [], i = 0) {
    if (n == ys.length) {
        fn([...ys]);
    } else if (xs.length - i >= n - ys.length) {
        ys.push(xs[i]);
        combination(fn, n, xs, ys, i + 1);
        ys.pop();
        combination(fn, n, xs, ys, i + 1);
    }
}

// 重複組み合わせ
function combination_with_repetition(fn, n, xs, ys = [], i = 0) {
    if (n == ys.length) {
        fn([...ys]);
    } else if (xs.length > i) {
        ys.push(xs[i]);
        combination_with_repetition(fn, n, xs, ys, i);
        ys.pop();
        combination_with_repetition(fn, n, xs, ys, i + 1);
    }
}

// 完全順列
// (0 .. m-1) の中から m 個を選ぶ
function derangement(fn, m, ps = [], flag = new Set()) {
    if (ps.length == m) {
        fn([...ps]);
    } else {
        for (let x = 0; x < m; x++) {
            if (x != ps.length && !flag.has(x)) {
                flag.add(x);
                ps.push(x);
                derangement(fn, m, ps, flag);
                ps.pop();
                flag.delete(x);
            }
        }
    }
}

// モンモール数
function montmort_number(n) {
    let a = 0n, b = 1n;
    for (let i = 1; i < n; i++) [a, b] = [b, BigInt(i + 1) * (a + b)]
    return a;
}

// 直積集合
function product_sub(fn, xs, i = 0, a = []) {
    if (i == xs.length) {
        fn([...a]);
    } else {
        for (let x of xs[i]) {
            a.push(x);
            product_sub(fn, xs, i + 1, a);
            a.pop();
        }
    }
}

function product(fn, ...args) {
    product_sub(fn, args);
}

export {
    iota, bag_of, factorial, permutation_number, permutation,
    combination_number, combination, derangement, montmort_number,
    product, permutation_with_repetition, combination_with_repetition
}

//
// test_comb_func.js : 順列と組み合わせのテスト
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
import * as M from './comb_func.js';
console.log("---- iota ----");
console.log(M.iota(0, 4));           // [0,1,2,3]
console.log(M.iota(0, 4, 2));        // [0,2,4,6]
console.log(M.iota(10n, 4, 1n));     // [10n, 11n, 12n, 13n,]
console.log(M.iota(10n, 4, -1n));    // [10n, 9n, 8n, 7n,]

console.log("---- factorial ----");
console.log(M.factorial(0));   // 1n
console.log(M.factorial(9));   // 362880n
console.log(M.factorial(10));  // 3628800n
console.log(M.factorial(15));  // 1307674368000n

console.log("---- permutation_number ----");
console.log(M.permutation_number(6, 1))   // 6
console.log(M.permutation_number(6, 3))   // 120
console.log(M.permutation_number(6, 6))   // 720
console.log(M.permutation_number(10, 4))  // 5040

console.log("---- permutation ----");
console.log(M.bag_of(M.permutation, 2, [1,2,3]));
console.log(M.bag_of(M.permutation, 3, [1,2,3]));
console.log(M.bag_of(M.permutation_with_repetition, 2, [1,2]));
console.log(M.bag_of(M.permutation_with_repetition, 2, [1,2,3]));

console.log("---- combination_number ----");
console.log(M.combination_number(5, 5))     // 1
console.log(M.combination_number(5, 3))     // 10
console.log(M.combination_number(5, 1))     // 5
console.log(M.combination_number(60, 30))   // 118264581564861424n

console.log("---- combination ----");
console.log(M.bag_of(M.combination, 1, [1,2,3,4,5]));
console.log(M.bag_of(M.combination, 3, [1,2,3,4,5]));
console.log(M.bag_of(M.combination, 5, [1,2,3,4,5]));
console.log(M.bag_of(M.combination_with_repetition, 2, [1,2]));
console.log(M.bag_of(M.combination_with_repetition, 2, [1,2,3]));

console.log("---- montmort_number ----");
console.log(M.montmort_number(3))     // 2
console.log(M.montmort_number(4))     // 9
console.log(M.montmort_number(5))     // 44
console.log(M.montmort_number(20))    // 895014631192902121n

console.log("---- derangement ----");
console.log(M.bag_of(M.derangement, 2));
console.log(M.bag_of(M.derangement, 3));
console.log(M.bag_of(M.derangement, 4));

console.log("---- product ----");
console.log(M.bag_of(M.product, [1,2,3,4]));
console.log(M.bag_of(M.product, [1,2],[3,4]));
console.log(M.bag_of(M.product, [1,2],[3,4,5]));
console.log(M.bag_of(M.product, [1,2],[3,4],[5,6]));

実行結果は同じなので省略します。速度は高階関数版の方が速いようです。

//
// test_comb.js : 簡単な速度比較
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
import * as G from './combination.js';
import * as H from './comb_func.js';

for (let size = 8; size <= 10; size++) {
    console.log(`----- ${size} -----`);
    let c = 0;
    var s = new Date().getTime();
    for (let xs of G.permutation(size, G.iota(0, size))) {
        c++;
    }
    var e = new Date().getTime();
    console.log(c, e - s);
    c = 0;
    s = new Date().getTime();
    H.permutation(x => c++, size, H.iota(0, size));
    var e = new Date().getTime();
    console.log(c, e - s);
}

$ node test_comb.js
----- 8 -----
40320 824
40320 53
----- 9 -----
362880 611
362880 192
----- 10 -----
3628800 6302
3628800 2011

●サンプルプログラム

魔方陣
問題の説明は Puzzle DE Programming: 魔方陣を参照

//
// magic.js : 魔方陣
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
import { permutation } from './combination.js';

// 盤面
// 0 1 2
// 3 4 5
// 6 7 8

// 直線
const lines = [
    [0,1,2], [3,4,5], [6,7,8],
    [0,3,6], [1,4,7], [2,5,8],
    [0,4,8], [2,4,6]
];

// 直線の和
function sum_line(xs, ls) {
    return ls.reduce((a, x) => a + xs[x], 0);
}

// チェック
function check(xs) {
    let sums = lines.map(ls => sum_line(xs, ls));
    return sums.every(x => x == sums[0]);
}

function print_board(xs) {
    console.log(`${xs[0]} ${xs[1]} ${xs[2]}`);
    console.log(`${xs[3]} ${xs[4]} ${xs[5]}`);
    console.log(`${xs[6]} ${xs[7]} ${xs[8]}\n`);
}

function solver() {
    for (let xs of permutation(9, [1,2,3,4,5,6,7,8,9])) {
        if (check(xs)) {
            print_board(xs);
        }
    }
}

// 実行
solver();

$ node magic.js
2 7 6
9 5 1
4 3 8

2 9 4
7 5 3
6 1 8

4 3 8
9 5 1
2 7 6

4 9 2
3 5 7
8 1 6

6 1 8
7 5 3
2 9 4

6 7 2
1 5 9
8 3 4

8 1 6
3 5 7
4 9 2

8 3 4
1 5 9
6 7 2

覆面算
問題の説明は Puzzle DE Programming: 覆面算を参照

//
// hukumen.js : send + more = money
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
import { permutation } from './combination.js';

// m = 1 は自明、s e n d o r y の値を求める
//               0 1 2 3 4 5 6
function solver() {
    for (let xs of permutation(7, [0,2,3,4,5,6,7,8,9])) {
        let send  = xs[0] * 1000 + xs[1] * 100 + xs[2] * 10 + xs[3];
        let more  = 1000 + xs[4] * 100 + xs[5] * 10 + xs[1];
        let money = 10000 + xs[4] * 1000 + xs[2] * 100 + xs[1] * 10 + xs[6];
        if (send + more == money) {
            console.log(`${send} + ${more} = ${money}`);
        }
    }
}

// 実行
solver();

$ node hukumen.js
9567 + 1085 = 10652

マスターマインド
問題の説明は Puzzle DE Programming: マスターマインドを参照

//
// master.js : マスターマインドの解法
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
import { permutation } from './combination.js';

// bulls を求める
function count_bulls(xs, ys) {
    let c = 0;
    for (let i = 0; i < xs.length; i++) {
        if (xs[i] == ys[i]) c++;
    }
    return c;
}

// 同じ数を数える
function count_same_number(xs, ys) {
    return xs.reduce((a, x) => ys.indexOf(x) != -1 ? a + 1 : a, 0);
}

// bulls と cows を求める
function count_bulls_cows(xs, ys) {
    let bulls = count_bulls(xs, ys);
    return [bulls, count_same_number(xs, ys) - bulls];
}

// 今までの質問と矛盾していないか
function check_query(xs, qs) {
    for (let [code, bulls, cows] of qs) {
        let [b, c] = count_bulls_cows(xs, code);
        if (b != bulls || c != cows) return false;
    }
    return true;
}

// 解法
function solver(answer) {
    let qs = [];
    for (let code of permutation(4, [0,1,2,3,4,5,6,7,8,9])) {
        if (check_query(code, qs)) {
            let [bulls, cows] = count_bulls_cows(code, answer);
            qs.push([code, bulls, cows]);
            console.log(`${qs.length}: ${code}, bulls ${bulls}, cows ${cows}`);
            if (bulls == 4) {
                console.log("Good Job!!\n");
                return;
            }
        }
    }
    console.log("Oops! maybe bug");
}

// 実行
solver([9,8,7,6]);
solver([5,2,9,3]);

$ node master.js
1: 0,1,2,3, bulls 0, cows 0
2: 4,5,6,7, bulls 0, cows 2
3: 5,4,8,9, bulls 0, cows 2
4: 6,7,9,8, bulls 0, cows 4
5: 8,9,7,6, bulls 2, cows 2
6: 9,8,7,6, bulls 4, cows 0
Good Job!!

1: 0,1,2,3, bulls 1, cows 1
2: 0,2,4,5, bulls 1, cows 1
3: 0,3,5,6, bulls 0, cows 2
4: 1,5,4,3, bulls 1, cows 1
5: 1,6,2,5, bulls 0, cows 2
6: 4,2,6,3, bulls 2, cows 0
7: 5,2,7,3, bulls 3, cows 0
8: 5,2,8,3, bulls 3, cows 0
9: 5,2,9,3, bulls 4, cows 0
Good Job!!

ライツアウト
問題の説明は Puzzle DE Programming: ライツアウトを参照

//
// lo.js : ライツアウトの解法
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
import { iota, combination } from './combination.js';

// ボタンを押したときのパターン
const pattern = [
    0x0000023, 0x0000047, 0x000008e, 0x000011c, 0x0000218,
    0x0000461, 0x00008e2, 0x00011c4, 0x0002388, 0x0004310,
    0x0008c20, 0x0011c40, 0x0023880, 0x0047100, 0x0086200,
    0x0118400, 0x0238800, 0x0471000, 0x08e2000, 0x10c4000,
    0x0308000, 0x0710000, 0x0e20000, 0x1c40000, 0x1880000
];

// ボタンを押す
function push_buttons(xs, board) {
    return xs.reduce((a, x) => pattern[x] ^ a, board);
}

// 解の表示
function print_answer(xs) {
    let n = 0;
    for (let i = 0; i < 5; i++) {
        let s = "";
        for (let j = 0; j < 5; j++) {
            s += xs.indexOf(n++) != -1 ? "O " : ". ";
        }
        console.log(s);
    }
    console.log("");
}

// 単純版
function solver_lo(board) {
    let zs = iota(0, 25);
    for (let n = 1; n <= 25; n++) {
        console.log(`-------- ${n} --------`);
        for (let xs of combination(n, zs)) {
            if (push_buttons(xs, board) == 0) {
                print_answer(xs);
                return true;
            }
        }
    }
    return false;
}

// 高速版
function solver_lo_fast(board) {
    for (let n = 1; n <= 5; n++) {
        for (let xs of combination(n, [0,1,2,3,4])) {
            let b = push_buttons(xs, board);
            for (let i = 5; i < 25; i++) {
                if ((b & (1 << (i - 5))) != 0) {
                    b ^= pattern[i];
                    xs.push(i);
                }
            }
            if (b == 0) print_answer(xs);
        }
    }
}

// 実行
console.log(solver_lo(0x1ffffff));
console.log(solver_lo_fast(0x1ffffff));

$ node lo.js
-------- 1 --------
-------- 2 --------
-------- 3 --------
-------- 4 --------
-------- 5 --------
-------- 6 --------
-------- 7 --------
-------- 8 --------
-------- 9 --------
-------- 10 --------
-------- 11 --------
-------- 12 --------
-------- 13 --------
-------- 14 --------
-------- 15 --------
O O . . .
O O . O O
. . O O O
. O O O .
. O O . O

true
O O . . .
O O . O O
. . O O O
. O O O .
. O O . O

. . . O O
O O . O O
O O O . .
. O O O .
O . O O .

O . O O .
. O O O .
O O O . .
O O . O O
. . . O O

. O O . O
. O O O .
. . O O O
O O . O O
O O . . .

undefined

●パズル「小町分数」

下図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。3 つの分数を足すと 1 / N になる配置を求めてください。

\( \dfrac{A}{BC} + \dfrac{D}{EF} + \dfrac{G}{HI} = \dfrac{1}{N} \)

ex)
3/27 + 6/54 + 9/81 = 1/3
3/54 + 6/72 + 9/81 = 1/4

図 : 小町分数 (1)

このパズルの元ネタは N = 1 の場合で、参考文献『超々難問数理パズル解けるものなら解いてごらん』に掲載されています。ちなみに、3 つの分数の和が整数になる場合、その値は 1 しかありません。また、値が 1 / N (N は整数) になる場合は 2, 3, 4, 6, 10 の 5 通りです。

プログラムは次のようになります。

//
// komachi_ratio.js : 小町分数
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
import Ratio from './ratio.js';
import { iota, permutation } from './combination.js';

function check(a, b, c, d, e, f, g, h, i) {
    let x = new Ratio(a, b * 10n + c);
    let y = new Ratio(d, e * 10n + f);
    let z = new Ratio(g, h * 10n + i);
    let r = x.add(y).add(z);
    if (a < d && d < g && r.numerator == 1n) {
        let s = `${a}/${b}${c} + ${d}/${e}${f} + ${g}/${h}${i} = ${r}`;
        console.log('%s', s);
    }
}

function komachi_ratio() {
    for (let xs of permutation(9, iota(1n, 9, 1n))) check(...xs);
}

// 実行
komachi_ratio();

基本的には単純な生成検定法ですが、分子の数字を a < d < g と限定することで、重複解を生成しないように工夫しています。それから、このプログラムでは 3 つの分数の和が 1 になる場合も解を出力します。プログラムを実行するときはご注意くださいませ。

$ node komachi_ratio.js
1/24 + 3/56 + 7/98 = 1/6
1/26 + 5/39 + 7/84 = 1/4
1/32 + 5/96 + 7/84 = 1/6
1/38 + 2/95 + 4/76 = 1/10
1/48 + 5/32 + 7/96 = 1/4
1/56 + 3/72 + 9/84 = 1/6
1/96 + 5/32 + 7/84 = 1/4
1/96 + 5/48 + 7/32 = 1/3
2/18 + 5/63 + 7/49 = 1/3
2/19 + 4/57 + 6/38 = 1/3
3/27 + 6/54 + 9/81 = 1/3
3/48 + 5/16 + 9/72 = 1/2
3/54 + 6/72 + 9/81 = 1/4
5/34 + 7/68 + 9/12 = 1

●ナルシシスト数

n 桁の自然数 m において、各桁の n 乗の和が m に等しい数を「ナルシシスト数 (narcissistic number)」といいます。定義により 1 桁の数 (1 - 9) はナルシシスト数になります。2 桁のナルシシスト数はありませんが、3 桁のナルシシスト数は以下の 4 つがあります。

153 = 1³ + 5³ + 3³ = 1 + 125 + 27 = 153
370 = 3³ + 7³ + 0³ = 27 + 343 + 0 = 370
371 = 3³ + 7³ + 1³ = 27 + 343 + 1 = 371
407 = 4³ + 0³ + 7³ = 64 + 0 + 343 = 407

ナルシシスト数は有限個しかありません。n 桁のナルシシスト数の最小値は 10^n-1 で、最大値は n * 9ⁿ です。ナルシシスト数が存在するには次の不等式が成立しないといけません。

10^n-1 <= n * 9ⁿ

両辺を 9^n-1 で割ると以下の式になります。

(10 / 9)^n-1 <= 9 * n

n が小さいとき上式は成立しますが、n が大きくなると指数関数の値は爆発的に増加するので、上式はいづれ不成立になります。具体的には n が 60 を超えると不成立になります。

n = 60: (10 / 9)⁵⁹ = 500.8327, 9 * 60 = 540, 成立
n = 61: (10 / 9)⁶⁰ = 556.4808, 9 * 61 = 549, 不成立

●プログラムの作成

ナルシシスト数を求める場合、たとえば 4 桁のナルシシスト数であれば、1000 - 9999 までの整数値を順番に生成し、各桁の 4 乗和の計算結果が元の整数と等しければ、その数はナルシシスト数と判定することができます。ただし、この方法はとても非効率です。1634 は 4 桁のナルシシスト数ですが、それ以外の数字の並び方 (23 通り) はナルシシスト数にはなりません。

各桁の n 乗和は数字の並びに関係なく計算することができるので、この場合は 0 - 9 から n 個の数字を選ぶ重複組み合わせを求めたほうが効率的です。選んだ数字の組み合わせから整数値を生成し、その値を桁ごとに分解した結果、元の組み合わせと同じであれば、その数をナルシスト数と判定することができます。

数値を桁に分解するプログラムは簡単です。プログラムと実行例を示します。

リスト : 数の分解

// 数を桁ごとに分解
function split_digit(n) {
    let a = [];
    while (n > 0n) {
        a.push(n % 10n);
        n /= 10n;
    }
    return a;
}

// 数字の個数をカウント
function count_number(xs) {
    let a = [0,0,0,0,0, 0,0,0,0,0];
    for (let x of xs) a[x]++;
    return a;
}

> split_digit(1634n)
[ 4n, 3n, 6n, 1n ]
> split_digit(45678n)
[ 8n, 7n, 6n, 5n, 4n ]
> split_digit(123123456n)
[
  6n, 5n, 4n, 3n, 2n,
  1n, 3n, 2n, 1n
]

> count_number(split_digit(1634n))
[
  0, 1, 0, 1, 1,
  0, 1, 0, 0, 0
]
> count_number(split_digit(45678n))
[
  0, 0, 0, 0, 1,
  1, 1, 1, 1, 0
]
> count_number(split_digit(123123456n))
[
  0, 2, 2, 2, 1,
  1, 1, 0, 0, 0
]

累乗和を求める場合、2 つの配列で畳み込みを行う関数 fold_left2 を用意すると簡単です。

リスト : 畳み込み

function fold_left2(fn, a, xs, ys) {
    let k = Math.min(xs.length, ys.length);
    for (let i = 0; i < k; i++) a = fn(a, xs[i], ys[i]);
    return a;
}

引数 xs に count_number の返り値を渡し、ys に累乗 i ** n (0 <= i < 10) を格納した配列を渡します。そして、関数 fn に (a, x, y) => a + x * y を、初期値 a に 0 を渡せば、累乗輪を求めることができます。

最後に n 桁のナルシシスト数を求める関数 solver を作ります。

リスト : n 桁のナルシシスト数を求める

function solver(n) {
    let ps = iota(0n, 10, 1n).map(x => x ** n);
    for (let xs of combination_with_repetition(n, iota(0, 10))) {
        let cs = count_number(xs);
        let x = fold_left2((a, x, y) => a += BigInt(x) * y, 0n, cs, ps);
        let ds = count_number(split_digit(x));
        if (equal_array(cs, ds)) console.log(x);
    }
}

最初に iota と map を使って、数の n 乗を格納した配列 ps を作ります。次に、combination_with_repetition で重複組み合わせを生成し、count_number で数字を数えて変数 cs にセットします。そして、累乗和を fold_left2 で求めて変数 x にセットします。

split_digit で x を桁ごとに分解し、count_number で数字を数え、結果を変数 ds にセットします。cs と ds が等しければ、x はナルシシスト数です。console.log で x を表示します。

それでは実行してみましょう。

$ node narci.js
----- 1 -----
1n
2n
3n
4n
5n
6n
7n
8n
9n
----- 2 -----
----- 3 -----
370n
407n
153n
371n
----- 4 -----
8208n
1634n
9474n
----- 5 -----
93084n
92727n
54748n
----- 6 -----
548834n
----- 7 -----
9800817n
4210818n
1741725n
9926315n
----- 8 -----
24678050n
24678051n
88593477n
----- 9 -----
146511208n
912985153n
472335975n
534494836n
----- 10 -----
4679307774n
----- 11 -----
32164049650n
40028394225n
42678290603n
49388550606n
32164049651n
94204591914n
44708635679n
82693916578n
----- 12 -----
----- 13 -----
----- 14 -----
28116440335967n
----- 15 -----
----- 16 -----
4338281769391370n
4338281769391371n
----- 17 -----
35875699062250035n
21897142587612075n
35641594208964132n
----- 18 -----

18 桁程度であれば JavaScript でもナルシシスト数を簡単に求めることができるようです。これ以上桁数を増やすには、より高速なプログラミング言語を使う、何かしらの枝刈りを入れる、あるいはその両方を行う必要があると思います。参考 URL 3 によると、ナルシシスト数は全部で 88 個あり、最大桁数は 39 になるそうです。deepgreen さんは、参考 URL 1 ですべてのナルシシスト数を求めています。興味のある方は挑戦してみてください。

●参考 URL

●プログラムリスト

//
// narci.js : ナルシスト数
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
//
import { iota, combination_with_repetition } from './combination.js';

// 数を桁ごとに分解
function split_digit(n) {
    let a = [];
    while (n > 0n) {
        a.push(n % 10n);
        n /= 10n;
    }
    return a;
}

// 数字の個数をカウント
function count_number(xs) {
    let a = [0,0,0,0,0, 0,0,0,0,0];
    for (let x of xs) a[x]++;
    return a;
}

// 畳み込み
function fold_left2(fn, a, xs, ys) {
    let k = Math.min(xs.length, ys.length);
    for (let i = 0; i < k; i++) a = fn(a, xs[i], ys[i]);
    return a;
}

// 配列が等しいか
function equal_array(xs, ys) {
    if (xs.length != ys.length) return false;
    for (let i = 0; i < xs.length; i++) {
        if (xs[i] != ys[i]) return false;
    }
    return true;
}

// n 桁のナルシスト数を求める
function solver(n) {
    let ps = iota(0n, 10, 1n).map(x => x ** n);
    for (let xs of combination_with_repetition(n, iota(0, 10))) {
        let cs = count_number(xs);
        let x = fold_left2((a, x, y) => a += BigInt(x) * y, 0n, cs, ps);
        let ds = count_number(split_digit(x));
        if (equal_array(cs, ds)) console.log(x);
    }
}

// 実行
for (let i = 1n; i <= 18n; i++) {
    console.log(`----- ${i} -----`);
    solver(i);
}

JavaScript Programming