Permutationを $N-1$ 回以下のswapでソートする
(Src/Sequence/PermutationSwapSort.hpp)

• View this file on GitHub
• Last update: 2025-04-06 19:32:49+09:00
• Include: #include "Src/Sequence/PermutationSwapSort.hpp"

概要

$(0,1,2,\dots, N-1)$ の並び替え $P$ を入力に与えると、 $N-1$ 回以下の(隣接とは限らない)二点swapでソートします。

なお、実際にソートは行われず操作列が返ります。

ライブラリの使い方

template <std::input_iterator It>
std::vector<std::pair<usize, usize>> PermutationSwapSort(It first, It last)

計算量: $O(N)$

• 順列であるかのチェックやstd::vectorへのコピーが行われるため、若干オーバーヘッドがあります

Depends on

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

Verified with

• Test/AtCoder/abc350_c.test.cpp
• Test/CF/CF1015-C.test.cpp

Code

#pragma once

#include <cassert>
#include <concepts>
#include <iterator>
#include <utility>
#include <vector>

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

namespace zawa {

namespace internal {

// Is A permutation of (0,1,...,|A|-1) ?
template <std::integral T>
bool IsPermutation(const std::vector<T>& A) {
    std::vector<bool> app(A.size());
    for (T v : A) {
        if (v < 0 or v >= (T)A.size()) return false;
        if (app[v]) return false;
        app[v] = true;
    }
    return true;
}

} // namespace internal

template <std::input_iterator It>
std::vector<std::pair<usize, usize>> PermutationSwapSort(It first, It last) {
    std::vector P(first, last);
    assert(internal::IsPermutation(P));
    std::vector<std::pair<usize, usize>> res;
    for (usize i = 0 ; i < P.size() ; i++) while ((usize)P[i] != i) {
        res.push_back({i, P[i]});
        std::swap(P[i], P[P[i]]);
    }
    return res;
}

} // namespace zawa

#line 2 "Src/Sequence/PermutationSwapSort.hpp"

#include <cassert>
#include <concepts>
#include <iterator>
#include <utility>
#include <vector>

#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 10 "Src/Sequence/PermutationSwapSort.hpp"

namespace zawa {

namespace internal {

// Is A permutation of (0,1,...,|A|-1) ?
template <std::integral T>
bool IsPermutation(const std::vector<T>& A) {
    std::vector<bool> app(A.size());
    for (T v : A) {
        if (v < 0 or v >= (T)A.size()) return false;
        if (app[v]) return false;
        app[v] = true;
    }
    return true;
}

} // namespace internal

template <std::input_iterator It>
std::vector<std::pair<usize, usize>> PermutationSwapSort(It first, It last) {
    std::vector P(first, last);
    assert(internal::IsPermutation(P));
    std::vector<std::pair<usize, usize>> res;
    for (usize i = 0 ; i < P.size() ; i++) while ((usize)P[i] != i) {
        res.push_back({i, P[i]});
        std::swap(P[i], P[P[i]]);
    }
    return res;
}

} // namespace zawa

Back to top page