permutation.hpp

Go to the documentation of this file.

// Copyright (c) 2019-2022 Simons Foundation
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0.txt
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Authors: Thomas Hahn, Olivier Parcollet, Nils Wentzell
 
#pragma once
 
#include "../macros.hpp"
#include "../stdutil/array.hpp"
#include "../stdutil/concepts.hpp"
 
#include <algorithm>
#include <array>
#include <concepts>
#include <cstddef>
#include <cstdint>
 
namespace nda {
 
  template <size_t N>
  constexpr std::array<int, N> decode(uint64_t binary_representation) {
    auto result = stdutil::make_initialized_array<N>(0);
    for (int i = 0; i < N; ++i) result[i] = (binary_representation >> (4 * i)) & 0b1111ull;
    return result;
  }
 
  template <size_t N>
  constexpr uint64_t encode(std::array<int, N> const &a) {
    uint64_t result = 0;
    for (int i = 0; i < N; ++i) {
      EXPECTS(0 <= a[i] and a[i] <= 15);
      result += (static_cast<uint64_t>(a[i]) << (4 * i));
    }
    return result;
  }
 
} // namespace nda
 
namespace nda::permutations {
 
  template <std::integral Int, size_t N>
  constexpr bool is_valid(std::array<Int, N> const &p) {
    auto idx_counts = stdutil::make_initialized_array<N>(0);
    for (auto idx : p) {
      if (idx < 0 or idx > N - 1 or idx_counts[idx] > 0) return false;
      idx_counts[idx] = 1;
    }
    return true;
  }
 
  template <std::integral Int, size_t N>
  constexpr std::array<Int, N> compose(std::array<Int, N> const &p1, std::array<Int, N> const &p2) {
    EXPECTS(is_valid(p1));
    EXPECTS(is_valid(p2));
    auto result = stdutil::make_initialized_array<N>(0);
    for (int u = 0; u < N; ++u) result[u] = p1[p2[u]];
    return result;
  }
 
  template <std::integral Int, size_t N>
  constexpr std::array<Int, N> inverse(std::array<Int, N> const &p) {
    EXPECTS(is_valid(p));
    auto result = stdutil::make_initialized_array<N>(0);
    for (int u = 0; u < N; ++u) result[p[u]] = u;
    return result;
  }
 
  template <typename T, std::integral Int, size_t N>
  constexpr std::array<T, N> apply_inverse(std::array<Int, N> const &p, std::array<T, N> const &a) {
    EXPECTS(is_valid(p));
    auto result = stdutil::make_initialized_array<N, T>(0);
    for (int u = 0; u < N; ++u) result[p[u]] = a[u];
    return result;
  }
 
  template <typename T, std::integral Int, size_t N>
  constexpr std::array<T, N> apply(std::array<Int, N> const &p, std::array<T, N> const &a) {
    EXPECTS(is_valid(p));
    auto result = stdutil::make_initialized_array<N, T>(0);
    for (int u = 0; u < N; ++u) result[u] = a[p[u]];
    return result;
  }
 
  template <size_t N>
  constexpr std::array<int, N> identity() {
    auto result = stdutil::make_initialized_array<N>(0);
    for (int i = 0; i < N; ++i) result[i] = i;
    return result;
  }
 
  template <size_t N>
  constexpr std::array<int, N> reverse_identity() {
    auto result = stdutil::make_initialized_array<N>(0);
    for (int i = 0; i < N; ++i) result[i] = N - 1 - i;
    return result;
  }
 
  template <size_t N>
  constexpr std::array<int, N> transposition(int i, int j) {
    auto r = identity<N>();
    r[i]   = j;
    r[j]   = i;
    return r;
  }
 
  template <size_t N>
  constexpr std::array<int, N> cycle(int p, int pos = N) {
    auto result = stdutil::make_initialized_array<N>(0);
    pos         = std::clamp(pos, 0, static_cast<int>(N));
    for (int i = 0; i < N; ++i) result[i] = (i < pos ? (pos + i - p) % pos : i);
    return result;
  }
 
} // namespace nda::permutations