Src/Random/RandomDistinctArray.hpp

• View this file on GitHub
• Last update: 2025-09-06 12:13:55+09:00
• Include: #include "Src/Random/RandomDistinctArray.hpp"

Depends on

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

Required by

• Src/Random/RandomBalancedParenthesis.hpp
• Src/Random/RandomConnectedGraph.hpp
• Src/Random/RandomTree.hpp

Code

#pragma once

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

#include <algorithm>
#include <cassert>
#include <concepts>
#include <vector>
#include <random>
#include <unordered_map>
#include <unordered_set>

#include <iostream>

namespace zawa {

namespace Random {

template <std::integral T>
std::vector<T> DistinctArray(usize n, T min, T max, bool verify = true) {
    assert(min <= max);
    assert(n <= static_cast<usize>(max - min + 1));
    std::mt19937_64 mt{std::random_device{}()};
    std::vector<T> res(n);
    std::unordered_map<T, T> mp;
    for (T& v : res) {
        T val = static_cast<T>(mt() % (max - min + 1)) + min;
        T replace = [&]() {
            auto it = mp.find(max);
            return it == mp.end() ? max : it->second;
        }();
        auto it = mp.find(val);
        if (it == mp.end()) {
            v = val;
            mp[val] = replace;
        }
        else {
            v = it->second;
            it->second = replace;
        }
        max--;
    }
    if (verify) {
        assert(std::ranges::all_of(res, [&](T v) { return min <= v and v <= static_cast<T>(max + n); }));
        assert(std::unordered_set<T>(res.begin(), res.end()).size() == n);
    }
    return res;
}

} // namespace Random

} // namespace zawa

#line 2 "Src/Random/RandomDistinctArray.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 4 "Src/Random/RandomDistinctArray.hpp"

#include <algorithm>
#include <cassert>
#include <concepts>
#include <vector>
#include <random>
#include <unordered_map>
#include <unordered_set>

#include <iostream>

namespace zawa {

namespace Random {

template <std::integral T>
std::vector<T> DistinctArray(usize n, T min, T max, bool verify = true) {
    assert(min <= max);
    assert(n <= static_cast<usize>(max - min + 1));
    std::mt19937_64 mt{std::random_device{}()};
    std::vector<T> res(n);
    std::unordered_map<T, T> mp;
    for (T& v : res) {
        T val = static_cast<T>(mt() % (max - min + 1)) + min;
        T replace = [&]() {
            auto it = mp.find(max);
            return it == mp.end() ? max : it->second;
        }();
        auto it = mp.find(val);
        if (it == mp.end()) {
            v = val;
            mp[val] = replace;
        }
        else {
            v = it->second;
            it->second = replace;
        }
        max--;
    }
    if (verify) {
        assert(std::ranges::all_of(res, [&](T v) { return min <= v and v <= static_cast<T>(max + n); }));
        assert(std::unordered_set<T>(res.begin(), res.end()).size() == n);
    }
    return res;
}

} // namespace Random

} // namespace zawa

Back to top page