После тасования в массиве, представляющим собой перестановку чисел 1..n, может быть несколько циклов (disjoint cycles)
Для обнаружения циклов можно сделать следующее:
Cканировать массив слева направо, пока не встретим ненулевой элемент
Запомним его позицию start
, положим k=start
Будем переходить на позицию A[k] - 1
, пока k
снова не станет равно start
- цикл завершён
По пути будем обнулять все элементы (пометка пройденных)
Продолжим сканировать, начиная с позиции start+1
, пока не найдём ненулевой элемент, и снова пойдём по циклу
[3, 1, 2, 4]
start = 0
k = 0
k = A[0] - 1 = 3-1 = 2; A[0] = 0
k = A[2] - 1 = 2-1 = 1; A[2] = 0
k = A[1] - 1 = 1-1 = 0 - вернулись к началу цикла; A[1]= 0
первый цикл обнаружен, содержит три элемента, они помечены.
[0, 0, 0, 4] находим start=3, указывает на себя же,
второй цикл из одного элемента