Factor a Permutation into Full Cycles
Autumn Tournament (2007)
Submission name: perm.cpp
Problem summary
Given a permutation f, first determine whether it is a single cycle containing all n elements. Otherwise express it as f=g∘h with both g and h full n-cycles, or report impossibility. Composition means f(i)=g(h(i)).
Input
n, followed by f(1),…,f(n).
Output
Print 1 and the full cycle of f if possible. Otherwise print 2 and full cycles of g and h, each starting with 1, or print 0 if no factorization exists.
Constraints
3≤n≤10000; the input is a valid permutation.
Worked example
Original statement sample.
Input
5 3 4 5 1 2
Output
1 1 3 5 2 4
Solution analysis
- Decompose f into disjoint cycles. If there is only one, output it immediately, as required. A full n-cycle has sign (−1)^(n−1), so a product of two full cycles is even. Consequently an odd permutation that is not already a full cycle must produce 0. The sign is odd exactly when the number of even-length disjoint cycles is odd.
- Construct local factorizations of every even component. For an odd-length cycle c, use g=c² and h=c⁻¹; both are full cycles on that component. Pair the even-length cycles. For a pair A=(a1,…,a2r) and B=(b1,…,b2s), define g by visiting A’s odd-indexed elements, B’s odd-indexed elements, A’s even-indexed elements, then B’s even-indexed elements. Computing h=g⁻¹f produces one cycle on their union.
- Finally splice these disjoint blocks together. Choose a vertex in the accumulated block and a vertex in the next block, and swap their outgoing g images. This joins the two g cycles; in h=g⁻¹f it swaps those two vertex values, joining the corresponding h cycles as well. Once every block is joined, build inverseG and set h[v]=inverseG[f[v]]. For the sample, f itself follows 1→3→5→2→4→1, so output 1 and that cycle.
Why it works
Parity rules out every rejected non-cycle. For odd cycles, c²c⁻¹=c and gcd(2,length)=1. For paired even cycles, the stated odd/even ordering gives a single g cycle, and tracing g⁻¹f alternates backward through both parity chains, visiting every element before returning. Splicing g by a domain transposition changes h by the same output transposition; transposing vertices in different cycles joins those cycles. Inductively both factors become full cycles while their product stays f.
Watch out. Composition order matters: h=g⁻¹f, not fg⁻¹. Prioritize output 1 when f is itself a full cycle, even if it has odd sign. Pair even-length cycles, not odd-length cycles, and print cycle order rather than the image array.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
void printCycle(const vector<int>&permutation){
int vertex=1;
bool first=true;
do{
if(!first){
cout<<' ';
}
first=false;
cout<<vertex;
vertex=permutation[vertex];
}
while(vertex!=1);
cout<<'\n';
}
int main(){
int n;
cin>>n;
vector<int>f(n+1);
for(int vertex=1;vertex<=n;vertex++){
cin>>f[vertex];
}
vector<bool>seen(n+1,false);
vector<vector<int>>odd,even;
int cycleCount=0;
for(int start=1;start<=n;start++){
if(seen[start]){
continue;
}
vector<int>cycle;
for(int vertex=start;!seen[vertex];vertex=f[vertex]){
seen[vertex]=true;
cycle.push_back(vertex);
}
cycleCount++;
if(cycle.size()%2==1){
odd.push_back(cycle);
}
else{
even.push_back(cycle);
}
}
if(cycleCount==1){
cout<<1<<'\n';
printCycle(f);
return 0;
}
if(even.size()%2==1){
cout<<0<<'\n';
return 0;
}
vector<int>g(n+1);
vector<int>representatives;
for(auto cycle:odd){
int size=static_cast<int>(cycle.size());
for(int i=0;i<size;i++){
g[cycle[i]]=cycle[(i+2)%size];
}
representatives.push_back(cycle[0]);
}
for(int block=0;block<static_cast<int>(even.size());block+=2){
vector<int>order;
for(int parity=0;parity<2;parity++){
for(int part=0;part<2;part++){
const auto&cycle=even[block+part];
for(int i=parity;i<static_cast<int>(cycle.size());i+=2){
order.push_back(cycle[i]);
}
}
}
for(int i=0;i<static_cast<int>(order.size());i++){
g[order[i]]=order[(i+1)%order.size()];
}
representatives.push_back(order[0]);
}
// Swapping images joins cycles in g and simultaneously in g^-1*f.
for(int i=1;i<static_cast<int>(representatives.size());i++){
swap(g[representatives[0]],g[representatives[i]]);
}
vector<int>inverseG(n+1),h(n+1);
for(int vertex=1;vertex<=n;vertex++){
inverseG[g[vertex]]=vertex;
}
for(int vertex=1;vertex<=n;vertex++){
h[vertex]=inverseG[f[vertex]];
}
cout<<2<<'\n';
printCycle(g);
printCycle(h);
}