Partition Matroid
(matroid/partition_matroid.hpp)

• View this file on GitHub
• Last update: 2026-07-01 14:07:14+09:00
• Include: #include "matroid/partition_matroid.hpp"

Overview

PartitionMatroid assigns every ground element to one group and limits how many elements may be selected from each group.

The one-argument constructor gives every group capacity one. The two-argument constructor accepts individual capacities.

Oracle inputs must contain distinct valid ground-set indices.

Interface

Method	Description	Complexity
PartitionMatroid(std::vector<int> group)	Creates capacity-one groups. Group ids must be non-negative and dense enough to allocate through the maximum id.	$O(N+G)$
PartitionMatroid(std::vector<int> group, std::vector<int> capacity)	Uses capacity[g] for group g.	$O(N+G)$
int size() const	Returns the ground-set size.	$O(1)$
int group_count() const	Returns the number of groups.	$O(1)$
const std::vector<int>& groups() const	Returns the group of every element.	$O(1)$
const std::vector<int>& capacities() const	Returns the capacities.	$O(1)$
bool independent(const std::vector<int>& subset) const	Checks all group capacities.	$O(G+	S	)$
bool operator()(const std::vector<int>& subset) const	Independence-oracle shorthand.	$O(G+	S	)$

Example

#include "matroid/partition_matroid.hpp"
#include <vector>

std::vector<int> group = {0, 0, 1, 1, 1};
std::vector<int> capacity = {1, 2};
m1une::matroid::PartitionMatroid matroid(group, capacity);

bool ok = matroid(std::vector<int>{0, 2, 4}); // true

Required by

• Matroid All (matroid/all.hpp)

Verified with

• verify/matroid/matroid_intersection.test.cpp
• verify/matroid/matroids.test.cpp
• verify/matroid/weighted_matroid_intersection.test.cpp

Code

#ifndef M1UNE_MATROID_PARTITION_MATROID_HPP
#define M1UNE_MATROID_PARTITION_MATROID_HPP 1

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace m1une {
namespace matroid {

class PartitionMatroid {
   private:
    std::vector<int> _group;
    std::vector<int> _capacity;

    void validate() const {
#ifndef NDEBUG
        for (int capacity : _capacity) assert(0 <= capacity);
        for (int group : _group) assert(0 <= group && group < int(_capacity.size()));
#endif
    }

   public:
    PartitionMatroid() = default;

    explicit PartitionMatroid(std::vector<int> group) : _group(std::move(group)) {
        int group_count = 0;
        for (int value : _group) {
            assert(0 <= value);
            group_count = std::max(group_count, value + 1);
        }
        _capacity.assign(group_count, 1);
    }

    PartitionMatroid(std::vector<int> group, std::vector<int> capacity)
        : _group(std::move(group)), _capacity(std::move(capacity)) {
        validate();
    }

    int size() const {
        return int(_group.size());
    }

    int group_count() const {
        return int(_capacity.size());
    }

    const std::vector<int>& groups() const {
        return _group;
    }

    const std::vector<int>& capacities() const {
        return _capacity;
    }

    bool independent(const std::vector<int>& subset) const {
        std::vector<int> count(_capacity.size(), 0);
        for (int element : subset) {
            assert(0 <= element && element < int(_group.size()));
            int group = _group[element];
            if (++count[group] > _capacity[group]) return false;
        }
        return true;
    }

    bool operator()(const std::vector<int>& subset) const {
        return independent(subset);
    }
};

}  // namespace matroid
}  // namespace m1une

#endif  // M1UNE_MATROID_PARTITION_MATROID_HPP

#line 1 "matroid/partition_matroid.hpp"



#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace m1une {
namespace matroid {

class PartitionMatroid {
   private:
    std::vector<int> _group;
    std::vector<int> _capacity;

    void validate() const {
#ifndef NDEBUG
        for (int capacity : _capacity) assert(0 <= capacity);
        for (int group : _group) assert(0 <= group && group < int(_capacity.size()));
#endif
    }

   public:
    PartitionMatroid() = default;

    explicit PartitionMatroid(std::vector<int> group) : _group(std::move(group)) {
        int group_count = 0;
        for (int value : _group) {
            assert(0 <= value);
            group_count = std::max(group_count, value + 1);
        }
        _capacity.assign(group_count, 1);
    }

    PartitionMatroid(std::vector<int> group, std::vector<int> capacity)
        : _group(std::move(group)), _capacity(std::move(capacity)) {
        validate();
    }

    int size() const {
        return int(_group.size());
    }

    int group_count() const {
        return int(_capacity.size());
    }

    const std::vector<int>& groups() const {
        return _group;
    }

    const std::vector<int>& capacities() const {
        return _capacity;
    }

    bool independent(const std::vector<int>& subset) const {
        std::vector<int> count(_capacity.size(), 0);
        for (int element : subset) {
            assert(0 <= element && element < int(_group.size()));
            int group = _group[element];
            if (++count[group] > _capacity[group]) return false;
        }
        return true;
    }

    bool operator()(const std::vector<int>& subset) const {
        return independent(subset);
    }
};

}  // namespace matroid
}  // namespace m1une

Back to top page