PermutationCycles

SRM 128 · 2003-01-06 · by vorthys

Class Name: PermutationCycles

Return Type: int

Method Name: cycles

Arg Types: (vector<int>)

Problem Statement

A permutation of size N is a rearrangement of the sequence 1,2,...,N such that no number is discarded or duplicated. A permutation can always be decomposed into a collection of disjoint cycles of the form (x₁ x₂ ... x_k), which means that the number x₁ is in position x₂, the number x₂ is in position x₃, and so on, up to the number x_k, which is in position x₁. Every number in the permutation appears in exactly one such cycle. For example, the permutation 3,5,4,1,2 can be decomposed into the cycles (1 4 3) and (2 5), because

the number 1 is in position 4,
the number 4 is in position 3,
the number 3 is in position 1,
the number 2 is in position 5, and
the number 5 is in position 2.

Note that positions in this definition start at one, not zero.

Create a class PermutationCycles containing a method cycles that takes an int[] permutation and returns the number of non-empty, disjoint cycles in permutation.

Notes

Any rotation of a cycle counts as the same cycle. For example, the cycle (1 4 3) can also be written (4 3 1) or (3 1 4).

Constraints

permutation contains between 1 and 20 elements, inclusive.
Every integer in permutation is between 1 and the number of elements in permutation, inclusive.
No integer appears more than once in permutation.

Examples

{ 3, 5, 4, 1, 2 }
Returns: 2

The example above.

{ 1, 2, 3, 5, 6, 4 }
Returns: 4

The cycles are (1), (2), (3), and (4 6 5).

{ 5, 4, 3, 2, 1 }
Returns: 3

The cycles are (1 5), (2 4), and (3).

{ 1 }
Returns: 1

{ 17, 19, 7, 3, 8, 6, 11, 5, 14, 20, 1, 2, 16, 9, 15, 4, 10, 18, 13, 12 }
Returns: 6

Submissions are judged against all 39 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PermutationCycles with a public method int cycles(vector<int> permutation) · 39 test cases · 2 s / 256 MB per case