グレイコードによる部分集合列挙
(Src/Utility/GreyCode.hpp)

• View this file on GitHub
• Last update: 2026-01-14 17:43:50+09:00
• Include: #include "Src/Utility/GreyCode.hpp"

概要

$0$ 以上 $2^n$ 未満の要素からなる順列であって、任意の隣接する $2$ 要素のpopcountの差が $1$ であるものを取得する。

これによって、例えばbit全探索で $\Theta (N2^{N})$ かかるパートを $O(2^N)$ に改善できる事があるかもしれない。

• あまり頭の良いことをしなくても、例えばDFSで $O(2^N)$ は達成できるのだが、グレイコードをしたほうが定数倍がよさそう

ライブラリの使い方

GreyCode

std::vector<std::pair<GreyCodeOp, usize>> GreyCode(usize n)

順列を得るための操作の命令の列が与えられる。 GreyCodeOpとは以下のようなenum classであり、secondに入っている非負整数(idxと呼ぶ)に応じて以下のような意味がある

enum class GreyCodeOp {
    Add, // 2^idxを足す
    Remove, // 2^idxを引く
    Access // 現在idxがある
};

計算量: $O(2^{n})$

EnumerateSubsetProduct

template <class S, class T>
requires concepts::SetOperator<S, T>
std::vector<typename S::Element> EnumerateSubsetProduct(const std::vector<typename T>& A)

先述のAdd, Removeの演算をSに与えたとき、 $2^{n}$ 個の要素を列挙して返す。

返り値の $i$ 番目の要素は $i$ の二進数表示で立っている桁が $S_i = \{ j_1, j_2, \dots, j_k \}$ だとしたとき、 $\prod_{j\in S_i} A_j$ である。

テンプレートの雛形

struct SPD {
    using Element = ;
    static Element identity() {
    } 
    static void add(Element& s, const T& v) {
    }
    static void remove(Element& s, const T& v) {
    }
};

ここで、removeとはlに含まれているrを削除する関数である。可換群の逆元を計算するのとは若干違うことに注意する必要があるかもしれない。

• たとえばaddが掛け算をする関数だったとして、removeに与えられる引数は、lがrの倍数であることが保証される。(そのため、整数で閉じていると考えてよい)

計算量

• $A$ の要素数を $N$ とする
• add, removeを合計 $2^N - 1$ 回呼び出す
• identity()を丁度一回呼び出す
• GreyCode(N)を一回呼び出す
• $+O(2^N)$

Depends on

• Set Operator (Src/Algebra/Action/SetOperator.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/CF/CF1070-F.test.cpp

Code

#pragma once

#include "../Template/TypeAlias.hpp"
#include "../Algebra/Action/SetOperator.hpp"

#include <bit>
#include <utility>
#include <vector>

namespace zawa {

enum class GreyCodeOp {
    Add,
    Remove,
    Access
};

std::vector<std::pair<GreyCodeOp, usize>> GreyCode(usize n) {
    std::vector<std::pair<GreyCodeOp, usize>> res;
    res.reserve(1 << (n + 1));
    usize cur = 0;
    res.emplace_back(GreyCodeOp::Access, cur);
    for (usize i = 1 ; i < (1u << n) ; i++) {
        usize nxt = i ^ (i >> 1);
        usize k = std::countr_zero<unsigned>(cur ^ nxt);
        if (cur & (1 << k))
            res.emplace_back(GreyCodeOp::Remove, k);
        else
            res.emplace_back(GreyCodeOp::Add, k);
        res.emplace_back(GreyCodeOp::Access, nxt);
        cur = nxt;
    }
    return res;
}

template <class S, class T>
requires concepts::SetOperator<S, T>
std::vector<typename S::Element> EnumerateSubsetProduct(const std::vector<T>& A) {
    std::vector<typename S::Element> res(1 << A.size());
    typename S::Element cur = S::identity();
    for (auto [type, idx] : GreyCode(A.size())) {
        switch (type) {
        case GreyCodeOp::Add:
            S::add(cur, A[idx]);
            break;
        case GreyCodeOp::Remove:
            S::remove(cur, A[idx]);
            break;
        case GreyCodeOp::Access:
            res[idx] = cur;
            break;
        }
    }
    return res;
}

} // namespace zawa

#line 2 "Src/Utility/GreyCode.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Algebra/Action/SetOperator.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class S, class T>
concept SetOperator = requires {
    typename S::Element;
    { S::identity() } -> std::same_as<typename S::Element>;
    { S::add(std::declval<typename S::Element&>(), std::declval<T>()) } -> std::same_as<void>;
    { S::remove(std::declval<typename S::Element&>(), std::declval<T>()) } -> std::same_as<void>;
};

} // namespace concepts

} // namespace zawa
#line 5 "Src/Utility/GreyCode.hpp"

#include <bit>
#include <utility>
#include <vector>

namespace zawa {

enum class GreyCodeOp {
    Add,
    Remove,
    Access
};

std::vector<std::pair<GreyCodeOp, usize>> GreyCode(usize n) {
    std::vector<std::pair<GreyCodeOp, usize>> res;
    res.reserve(1 << (n + 1));
    usize cur = 0;
    res.emplace_back(GreyCodeOp::Access, cur);
    for (usize i = 1 ; i < (1u << n) ; i++) {
        usize nxt = i ^ (i >> 1);
        usize k = std::countr_zero<unsigned>(cur ^ nxt);
        if (cur & (1 << k))
            res.emplace_back(GreyCodeOp::Remove, k);
        else
            res.emplace_back(GreyCodeOp::Add, k);
        res.emplace_back(GreyCodeOp::Access, nxt);
        cur = nxt;
    }
    return res;
}

template <class S, class T>
requires concepts::SetOperator<S, T>
std::vector<typename S::Element> EnumerateSubsetProduct(const std::vector<T>& A) {
    std::vector<typename S::Element> res(1 << A.size());
    typename S::Element cur = S::identity();
    for (auto [type, idx] : GreyCode(A.size())) {
        switch (type) {
        case GreyCodeOp::Add:
            S::add(cur, A[idx]);
            break;
        case GreyCodeOp::Remove:
            S::remove(cur, A[idx]);
            break;
        case GreyCodeOp::Access:
            res[idx] = cur;
            break;
        }
    }
    return res;
}

} // namespace zawa

Back to top page