Statistics

Problem Statement for "PermutationCycles"

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 (x1 x2 ... xk), which means that the number x1 is in position x2, the number x2 is in position x3, and so on, up to the number xk, which is in position x1. 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.

Definition

Class:
PermutationCycles
Method:
cycles
Parameters:
int[]
Returns:
int
Method signature:
int cycles(int[] permutation)
(be sure your method is public)

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

  1. { 3, 5, 4, 1, 2 }

    Returns: 2

    The example above.

  2. { 1, 2, 3, 5, 6, 4 }

    Returns: 4

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

  3. { 5, 4, 3, 2, 1 }

    Returns: 3

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

  4. { 1 }

    Returns: 1

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

    Returns: 6

  6. { 1, 2, 3, 4, 5 }

    Returns: 5

  7. { 3, 4, 1, 6, 9, 2, 5, 7, 8}

    Returns: 3

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

    Returns: 1

  9. { 3, 4, 5, 6, 7, 8, 9, 10, 1, 2 }

    Returns: 2

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

    Returns: 20

  11. { 4, 3, 2, 7, 6, 5, 10, 9, 8, 1 }

    Returns: 4

  12. { 2, 1 }

    Returns: 1

  13. { 1, 2 }

    Returns: 2

  14. { 15, 14, 13, 12, 11, 1, 2, 3, 4, 5, 10, 9, 8, 7, 6 }

    Returns: 5

  15. { 5, 6, 7, 8, 9, 10, 11, 1, 2, 3, 4 }

    Returns: 1

  16. { 1, 9, 6, 5, 7, 2, 10, 12, 11, 3, 4, 8 }

    Returns: 3

  17. { 6, 3, 9, 7, 4, 10, 5, 2, 8, 1 }

    Returns: 3

  18. { 4, 2, 6, 8, 10, 7, 1, 3, 9, 5 }

    Returns: 4

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

    Returns: 2

  20. { 5, 4, 10, 7, 3, 6, 2, 13, 11, 1, 12, 9, 8 }

    Returns: 5

  21. { 2, 4, 6, 8, 10, 1, 3, 5, 7, 9 }

    Returns: 1

  22. { 1, 2, 3 }

    Returns: 3

  23. { 4, 5, 3, 2, 1, 6 }

    Returns: 3

  24. { 2, 3, 4, 5, 1, 6 }

    Returns: 2

  25. { 1, 2, 4, 3, 7, 6, 9, 5, 10, 8 }

    Returns: 5

  26. { 2, 3, 4, 5, 1 }

    Returns: 1

  27. { 2, 3, 4, 1 }

    Returns: 1

  28. { 1, 2, 3, 5, 11, 6, 4, 7, 10, 8, 9, 12 }

    Returns: 6

  29. { 4, 5, 1, 2, 3 }

    Returns: 1

  30. { 5, 4, 3, 2, 1 }

    Returns: 3

  31. { 1, 2, 3 }

    Returns: 3

  32. { 4, 5, 3, 2, 1, 6 }

    Returns: 3

  33. { 2, 3, 4, 5, 1, 6 }

    Returns: 2

  34. { 1, 2, 4, 3, 7, 6, 9, 5, 10, 8 }

    Returns: 5

  35. { 2, 3, 4, 5, 1 }

    Returns: 1

  36. { 2, 3, 4, 1 }

    Returns: 1

  37. { 1, 2, 3, 5, 11, 6, 4, 7, 10, 8, 9, 12 }

    Returns: 6

  38. { 4, 5, 1, 2, 3 }

    Returns: 1

  39. { 5, 4, 3, 2, 1 }

    Returns: 3

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: