Lexicographic Index of Permutations (in Factorial Number System)
(misc/permutation.hpp)

• View this file on GitHub
• Last update: 2024-01-08 00:27:17+09:00
• Include: #include "misc/permutation.hpp"

Depends on

• Fenwick Tree (data-structure/fenwick_tree.hpp)

Code

#pragma once
#include <vector>

#include "../data-structure/fenwick_tree.hpp"

/**
 * @brief Lexicographic Index of Permutations (in Factorial Number System)
 */

struct AddMonoid {
    using T = int;
    static T id() { return 0; }
    static T op(T a, T b) { return a + b; }
};

std::vector<int> perm_to_num(const std::vector<int>& p) {
    const int n = p.size();
    std::vector<int> num(n);
    FenwickTree<AddMonoid> ft(n);
    for (int i = n - 1; i >= 0; --i) {
        ft.update(p[i], 1);
        num[n - i - 1] = ft.prefix_fold(p[i]);
    }
    return num;
}

std::vector<int> num_to_perm(const std::vector<int>& num) {
    const int n = num.size();
    std::vector<int> p(n);
    FenwickTree<AddMonoid> ft(n);
    for (int i = 0; i < n; ++i) ft.update(i, 1);
    for (int i = 0; i < n; ++i) {
        p[i] = ft.lower_bound(num[n - i - 1] + 1);
        ft.update(p[i], -1);
    }
    return p;
}

#line 2 "misc/permutation.hpp"
#include <vector>

#line 2 "data-structure/fenwick_tree.hpp"
#include <functional>
#line 4 "data-structure/fenwick_tree.hpp"

template <typename M>
class FenwickTree {
    using T = M::T;

   public:
    FenwickTree() = default;
    explicit FenwickTree(int n) : n(n), data(n + 1, M::id()) {}

    T prefix_fold(int i) const {
        T ret = M::id();
        for (; i > 0; i -= i & -i) ret = M::op(ret, data[i]);
        return ret;
    }

    void update(int i, const T& x) {
        for (++i; i <= n; i += i & -i) data[i] = M::op(data[i], x);
    }

    int lower_bound(const T& x) const { return lower_bound(x, std::less<>()); }

    template <typename Compare>
    int lower_bound(const T& x, Compare cmp) const {
        if (!cmp(M::id(), x)) return 0;
        int k = 1;
        while (k * 2 <= n) k <<= 1;
        int i = 0;
        T v = M::id();
        for (; k > 0; k >>= 1) {
            if (i + k > n) continue;
            T nv = M::op(v, data[i + k]);
            if (cmp(nv, x)) {
                v = nv;
                i += k;
            }
        }
        return i + 1;
    }

   private:
    int n;
    std::vector<T> data;
};
#line 5 "misc/permutation.hpp"

/**
 * @brief Lexicographic Index of Permutations (in Factorial Number System)
 */

struct AddMonoid {
    using T = int;
    static T id() { return 0; }
    static T op(T a, T b) { return a + b; }
};

std::vector<int> perm_to_num(const std::vector<int>& p) {
    const int n = p.size();
    std::vector<int> num(n);
    FenwickTree<AddMonoid> ft(n);
    for (int i = n - 1; i >= 0; --i) {
        ft.update(p[i], 1);
        num[n - i - 1] = ft.prefix_fold(p[i]);
    }
    return num;
}

std::vector<int> num_to_perm(const std::vector<int>& num) {
    const int n = num.size();
    std::vector<int> p(n);
    FenwickTree<AddMonoid> ft(n);
    for (int i = 0; i < n; ++i) ft.update(i, 1);
    for (int i = 0; i < n; ++i) {
        p[i] = ft.lower_bound(num[n - i - 1] + 1);
        ft.update(p[i], -1);
    }
    return p;
}

Back to top page