2要素の分離を網羅するテクニック
(Src/Utility/SeparatedFamilySet.hpp)

• View this file on GitHub
• Last update: 2025-05-10 20:51:44+09:00
• Include: #include "Src/Utility/SeparatedFamilySet.hpp"
• Link: https://noshi91.hatenablog.com/entry/2024/05/31/012055

$U = { 0, 1, 2, \dots, U - 1}$ に対してある集合属 $S \subseteqq 2^{U}$ を計算する。 $S$ は以下の条件を満たす。

• 任意の $x, y\in U, x \ne y$ に対してある $s\in S$ が存在して $x\in s, y\notin s$ である。
• 条件を満たす $S$ は沢山あるが、そのなかで $\text{card}(S)$ が最小のものを一つ計算する。

計算量: $O(U\log U)$

• $\text{card}(S) \in \log_{2}U + O(\log \log U)$ らしい

ライブラリの使い方

std::vector<std::vector<bool>> SeparatedFamilySet(usize U)

長さ $U$ のstd::vector<bool>を $\text{card}(S)$ 個並べたstd::vectorを返す。

res[i][j] は $i$ 番目の集合に $j$ が属しているか。

参考

• 2要素の分離を網羅するテクニック

Depends on

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

Verified with

• Test/UC/3-36-F.test.cpp

Code

#pragma once

#include <algorithm>
#include <vector>
#include <concepts>
#include <ranges>

#include "../Template/TypeAlias.hpp"

namespace zawa {

// https://noshi91.hatenablog.com/entry/2024/05/31/012055
// 向きのついた分割
std::vector<std::vector<bool>> SeparatedFamilySet(usize U) {
    const usize d = [&]() {
        for (usize i = 1 ; ; i++) {
            usize max = 1;
            for (usize j = 0 ; j < (i / 2) ; j++) {
                max *= i - j;
                max /= j + 1;
            }
            if (max >= U) return i;
        }
        return U;
    }();
    std::vector res(d, std::vector<bool>(U));
    std::vector<u8> in(d);
    std::fill(in.rbegin(), in.rbegin() + d / 2, true);
    for (usize idx = 0 ; idx < U ; idx++) {
        for (usize i = 0 ; i < d ; i++) if (in[i]) {
            res[i][idx] = true;
        }
        std::ranges::next_permutation(in);
    }
    return res;
}

} // namespace zawa

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

#include <algorithm>
#include <vector>
#include <concepts>
#include <ranges>

#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 9 "Src/Utility/SeparatedFamilySet.hpp"

namespace zawa {

// https://noshi91.hatenablog.com/entry/2024/05/31/012055
// 向きのついた分割
std::vector<std::vector<bool>> SeparatedFamilySet(usize U) {
    const usize d = [&]() {
        for (usize i = 1 ; ; i++) {
            usize max = 1;
            for (usize j = 0 ; j < (i / 2) ; j++) {
                max *= i - j;
                max /= j + 1;
            }
            if (max >= U) return i;
        }
        return U;
    }();
    std::vector res(d, std::vector<bool>(U));
    std::vector<u8> in(d);
    std::fill(in.rbegin(), in.rbegin() + d / 2, true);
    for (usize idx = 0 ; idx < U ; idx++) {
        for (usize i = 0 ; i < d ; i++) if (in[i]) {
            res[i][idx] = true;
        }
        std::ranges::next_permutation(in);
    }
    return res;
}

} // namespace zawa

Back to top page