Как превратить массив целых чисел в перестановку и посчитать в нем циклы?

Question

Я проверял это по сети и спрашивал друзей, так как я очень плохо знаком с кодированием.Я нахожу все эти посты о написании всех возможных перестановок на n букв.Я не ищу этого.

То, что я пытаюсь достичь, - это массив целых чисел, я хочу превратить это в перестановку следующим образом.Скажем, X - это массив целых чисел:

X = {3, 4, 1, 2, 5}

Теперь люди, знакомые с группами перестановок (или симметричной группой), будут знать, что существует циклобозначение для любой перестановки.Я хочу видеть X как некоторую функцию, которая присваивает значения следующим образом:

1 -> 3

2 -> 4

3 -> 1

4 -> 2

5 -> 5

Таким образом, если указанная выше функция является сигмой перестановки, то мы имеем sigma (1) = 1-ю запись в X, sigma (2) = 2-я запись в X и т. д.

И, наконец, мне нужно посчитать, сколько циклов будет в этой перестановке, или количество циклов в обозначении циклов.Снова для примера выше, у нас есть

1 -> 3 -> 1 (так что это один цикл)

2 -> 4 -> 2 (другой цикл)

5 -> 5 (это также цикл)

Так что следует также сказать, что в этом случае X имеет 3 цикла.

Это может быть подробнымвопрос, но любой, хоть немного, помощь приветствуется.Спасибо всем ооочень большое!

Answer 1

Массив целых чисел уже является перестановкой, смещенной только на единицу, поскольку массивы в C индексируются нулем.Вы можете перебирать этот массив / перестановку p в цикле;как только вы увидите элемент x, который не принадлежит ни одному известному циклу, непрерывно вычисляйте p[x], p[p[x]], ..., пока не вернетесь к x (вычтите 1 при выполнении этого в коде C, чтобы учесть нулевое индексированиемассивов C).Это один цикл;учитывать этот цикл и перейти к следующему элементу.Код C представлен ниже.

Другой способ - преобразовать перестановку в график и подсчитать количество подключенных компонентов в графике, как это сделано здесь .

#include <stdio.h>
#include <stdbool.h>

unsigned count_cycles(const unsigned permutation[], const unsigned n)
{
    unsigned num_cycles = 0;
    bool visited[n];
    unsigned i;

    // initially, no elements are visited
    for(i = 0; i < n; ++i) {
        visited[i] = false;
    }

    // iterate through all elements
    for(i = 0; i < n; ++i) {
        if(!visited[i]) {
            // found a new cycle; mark all elements in it as visited
            int x = i;
            do {
                visited[x] = true;
                x = permutation[x] - 1;
            } while(!visited[x]);
            // account for the new cycle
            num_cycles++;
        }
    }

    return num_cycles;
}

int main()
{
    const unsigned permutation[] = { 3, 4, 1, 2, 5};
    const unsigned N = 5;
    printf("%u\n", count_cycles(permutation, N)); // prints "3"
}