0

Перестановка осуществляется следующим образом. Как посчитать количество циклов в ней?

    public static void main(String[] args)
{
    int[] array = { 1, 2, 3, 4 };
    Random rand = new Random();
    for (int i = array.length - 1; i > 0; i--)
    {
      int index = rand.nextInt(i + 1);
      int swap = array[index];
      array[index] = array[i];
      array[i] = swap;
    }
2
  • Каких циклов? Сколько раз будет выполняться цикл for? 8 окт 2018 в 16:00
  • Нет, циклов в перестановке
    – Alex
    9 окт 2018 в 7:03

1 ответ 1

1

После тасования в массиве, представляющим собой перестановку чисел 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, указывает на себя же, 
второй цикл из одного элемента
5
  • @Alex Получилось реализовать?
    – MBo
    10 окт 2018 в 10:24
  • к сожалению, нет
    – Alex
    13 окт 2018 в 18:04
  • 1
    А в чём трудность?
    – MBo
    14 окт 2018 в 3:58
  • не понятно почему этот алгоритм работает с математической точки зрения
    – Alex
    14 окт 2018 в 7:41
  • Хм.. А что такое цикл? Это последовательность, хвост которой указывает на начало. Вот это свойство и используется.
    – MBo
    14 окт 2018 в 12:48

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.