permute.cpp

#include <iostream>
#include <vector>
#include <set>

/// `_sigma` denotes a vector of size say `n`.
/// Corresponds to a permutation of {0, 1, 2, ..., n - 1}
/// The value `_sigma[i]` means `i` is mapped to `_sigma[i]`.
///
/// A cycle is a set {a_1, a_2, ..., a_N} such that
/// a_1 -> a_2; a_2 -> a_3, ..., a_{N-1} -> a_N; a_N -> a_1
/// (assuming that a_1, ..., a_N) are disjoint
///
/// (A) The algorithm first converts the permutation `_sigma` into
/// 'product of disjoint cycles'
///
/// For example, for _sigma = {3, 2, 1, 0}
///   Permutation: 0 1 2 3
///                3 2 1 0
///
/// Converts into cycles {0, 3} and {1, 2}
///
///
/// Represent swapN by the 2-cycle {0, N}
/// For example, {0, 3} is same as swap3
///
/// (B) Notice that a cycle {a_1, a_2, ..., a_N}
/// is the same as the product
/// {a_1, a_N} . {a_1, a_{N-1}} ... {a_1, a_2}
///
/// (C) About converting {x, y} into swapN when x and y are not 0:
/// {x, y} = {0, x} . {0, y} . {0, x} = {0, y} . {0, x}. {0, y}
///
///
/// Now we have everything to convert a permutation into swaps
/// 1. Convert it into product of disjoint cycles (A)
/// 2. Convert each cycle into 2-cycle (B)
/// 3. Convert each 2-cycle into swapN (C) if one of the element is non-zero
///
/// Above example
/// {0, 3} . {1, 2} => swap3, swap1, swap2, swap1
///
void permute(std::vector<unsigned> _sigma)
{
    // TODO Validate the input vector
    std::vector<std::vector<unsigned>> permutation;

    std::set<unsigned> toVisit(_sigma.begin(), _sigma.end());
    std::vector<unsigned> currentCycle;

    while(!toVisit.empty())
    {
        unsigned index = *toVisit.begin();
        currentCycle.push_back(index);
        toVisit.erase(index);

        while(_sigma[index] != currentCycle[0])
        {
            toVisit.erase(_sigma[index]);
            currentCycle.push_back(_sigma[index]);
            index = _sigma[index];
        }

        permutation.push_back(currentCycle);
        currentCycle.clear();
    }

    for(const auto& vec: permutation)
    {
        for(auto elem: vec)
        {
            std::cout << elem << " ";
        }
        std::cout << "\n";
    }
}

int main()
{
    std::vector<unsigned> sigma{3, 2, 1, 0};
    permute(sigma);
    // 0 3
    // 1 2

    std::vector<unsigned> sigma1{4, 2, 3, 0, 1};
    permute(sigma1);
    // A single cycle
    // 0 4 1 2 3
    // Decompose into
    // {0, 3}, {0, 2}, {0, 1}, {0, 4}
    // swap3, swap2, swap1, swap4

    std::vector<unsigned> sigma2{5, 4, 2, 3, 6, 0, 1};
    permute(sigma2);
    // Cycles
    // 0 5
    // 1 4 6
    // 2
    // 3
    // conversion
    // {0, 5} = swap5
    // {1, 4, 6} = {1, 6} . {1, 4}
    //           = {0, 1} . {0, 6} . {0, 1} . {0, 1} . {0, 4}. {0, 1} = {0, 1} . {0, 6} . {0, 4} . {0, 1}
    //           = swap1, swap6, swap4, swap1
    // 2 nothing
    // 3 nothing
    //
    // Final: swap5, swap1, swap6, swap4, swap1
}