$ 0 \leq p_{i} < a_{i} $ を満たす整数列 $p$ の列挙
(enumerate/enumerate_product.hpp)

• View this file on GitHub
• Last update: 2026-04-11 01:00:23+09:00
• Include: #include "enumerate/enumerate_product.hpp"

enumerate_product

void enumerate_product(std::vector<int> a, F f)

長さ $n$ の整数列 $a$ と std::vector<int> を引数にとる関数オブジェクト $f$ が与えられたとき、 $ i = 0, …, n - 1 $ について $ 0 \leq p_{i} < a_{i} $ を満たす整数列 $p$ を列挙し、それぞれの $p$ に対して $ f(p) $ を実行します。

例えば $p$ を std::vector<std::vector<int>> に格納する場合、$f$ は以下のようになります。

auto f = [&](std::vector<int> p) -> void {
    ps.push_back(p);
    return;
};

制約

• $a_{i}$ は int 型で表現可能

計算量

$f$ が定数時間で計算できると仮定したとき

• $ O \left( \prod_{i=0}^{n-1} a_{i} \right) $

$f$ の計算は多くの場合において $O(n)$ 以上必要です。

Verified with

• enumerate/test/enumerate_product.test.cpp

Code

#pragma once

#include <cassert>
#include <vector>

// enumerate product
// enumerate p (0 <= p[i] < a[i])
template <class F> void enumerate_product(std::vector<int> a, F f) {
    const int n = (int)(a.size());
    std::vector<int> p;
    auto dfs = [&](auto g, int i) -> void {
        if (i == n) {
            f(p);
            return;
        }
        for (int x = 0; x < a[i]; x++) {
            p.push_back(x);
            g(g, i + 1);
            p.pop_back();
        }
    };
    dfs(dfs, 0);
    return;
}

#line 2 "enumerate/enumerate_product.hpp"

#include <cassert>
#include <vector>

// enumerate product
// enumerate p (0 <= p[i] < a[i])
template <class F> void enumerate_product(std::vector<int> a, F f) {
    const int n = (int)(a.size());
    std::vector<int> p;
    auto dfs = [&](auto g, int i) -> void {
        if (i == n) {
            f(p);
            return;
        }
        for (int x = 0; x < a[i]; x++) {
            p.push_back(x);
            g(g, i + 1);
            p.pop_back();
        }
    };
    dfs(dfs, 0);
    return;
}

Back to top page