Cyclic Permutation(巡回置換分解)
(src/algorithm/Cyclic-Permutation.hpp)

• View this file on GitHub
• Last update: 2022-07-30 20:12:45+09:00
• Include: #include "src/algorithm/Cyclic-Permutation.hpp"

概要

std::vector<std::vector<int>> decomp_cyclic_permutation(std::vector<T>& arr)

引数の配列からソート済の列への置換を巡回置換の積で表現します。

機能

• decomp_cyclic_permutation(std::vector<T>& arr): 巡回置換に分解し、std::vector<std::vector<int>>の形で返します。0-indexedです。

使いどころ

• 列をソートするために必要な二項間swapの最小回数はN - 連結成分の数です。

• 他にもこのメモのようなな使いみちがあります

• 元記事

計算量

配列の長さを$N$として$O(N)$

Verified with

• test/aoj_alds_6_D.test.cpp

Code

#pragma once

#include <vector>
#include <algorithm>

namespace zawa {

    template <typename T>
    std::vector<std::vector<int>> decomp_cyclic_permutation(std::vector<T>& arr) {
        std::vector<std::pair<T, int>> cp(arr.size());
        for (int i = 0 ; i < (int)arr.size() ; i++) {
            cp[i] = {arr[i], i};
        }
        sort(cp.begin(), cp.end());

        std::vector<std::vector<int>> res;
        std::vector<int> used(arr.size());
        for (int i = 0 ; i < (int)arr.size() ; i++) {
            if (used[i]) continue;
            std::vector<int> cycle;
            int now = i;
            while(!used[now]) {
                cycle.emplace_back(now);
                used[now] = 1;
                now = cp[now].second;
            }
            res.emplace_back(cycle);
        }

        return res;
    }

}// namespace zawa

#line 2 "src/algorithm/Cyclic-Permutation.hpp"

#include <vector>
#include <algorithm>

namespace zawa {

    template <typename T>
    std::vector<std::vector<int>> decomp_cyclic_permutation(std::vector<T>& arr) {
        std::vector<std::pair<T, int>> cp(arr.size());
        for (int i = 0 ; i < (int)arr.size() ; i++) {
            cp[i] = {arr[i], i};
        }
        sort(cp.begin(), cp.end());

        std::vector<std::vector<int>> res;
        std::vector<int> used(arr.size());
        for (int i = 0 ; i < (int)arr.size() ; i++) {
            if (used[i]) continue;
            std::vector<int> cycle;
            int now = i;
            while(!used[now]) {
                cycle.emplace_back(now);
                used[now] = 1;
                now = cp[now].second;
            }
            res.emplace_back(cycle);
        }

        return res;
    }

}// namespace zawa

Back to top page