次の組み合わせを生成する
(ugilib/iteration/next_combination.hpp)

• View this file on GitHub
• Last update: 2024-04-03 22:46:30+09:00
• Include: #include "ugilib/iteration/next_combination.hpp"

Depends on

• ugilib/base/definitions.hpp

Required by

• 全ての順列/組み合わせに対する処理を簡略化する関数 (ugilib/iteration/all_combinations.hpp)

Verified with

• tests/iteration/combinations.test.cpp

Code

#pragma once
#include <bits/stdc++.h>
#include "ugilib/base/definitions.hpp"

using namespace std;

namespace ugilib {
    /**
     * @brief 次の組み合わせを生成する
     * @param indices 現在の組み合わせ
     * @param num_items 全体の要素数
     * @return bool 次の組み合わせが存在するかどうか
     * @details 例えば, indices = {0, 1, 2}, num_items = 5の場合, 次の組み合わせは{0, 1, 3}となる
     * @details これをラップしたものがexec_all_combination
    */
    bool next_combination(vector<size_t> &indices, const size_t &num_items) {
        const int num_pick = indices.size();
        for (signed i = num_pick - 1; i >= 0; i--) {
            if (indices[i] < num_items - num_pick + i) {
                indices[i]++;
                for (size_t j = i + 1; j < num_pick; j++) {
                    indices[j] = indices[j - 1] + 1;
                }
                return true;
            }
        }
        return false;
    }
} // namespace ugilib

#line 2 "ugilib/iteration/next_combination.hpp"
#include <bits/stdc++.h>
#line 2 "ugilib/base/definitions.hpp"

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i, n) for(size_t i = 0; i < n; i++)  // rep macro
#define all(v) begin(v), end(v)  // all iterator
#line 4 "ugilib/iteration/next_combination.hpp"

using namespace std;

namespace ugilib {
    /**
     * @brief 次の組み合わせを生成する
     * @param indices 現在の組み合わせ
     * @param num_items 全体の要素数
     * @return bool 次の組み合わせが存在するかどうか
     * @details 例えば, indices = {0, 1, 2}, num_items = 5の場合, 次の組み合わせは{0, 1, 3}となる
     * @details これをラップしたものがexec_all_combination
    */
    bool next_combination(vector<size_t> &indices, const size_t &num_items) {
        const int num_pick = indices.size();
        for (signed i = num_pick - 1; i >= 0; i--) {
            if (indices[i] < num_items - num_pick + i) {
                indices[i]++;
                for (size_t j = i + 1; j < num_pick; j++) {
                    indices[j] = indices[j - 1] + 1;
                }
                return true;
            }
        }
        return false;
    }
} // namespace ugilib

Back to top page