c-如何将一个整数数组变成一个排列，并计算其中的循环数

Question

我一直在网上查看它，并询问朋友，因为我对编码很陌生。我发现所有这些关于在n个字母上写所有可能的排列的帖子。我不想那样。

我试图实现的是给定一个整数数组，我想把它变成一个排列，如下所示。假设X是一个整数数组；

X＝｛3，4，1，2，5｝

现在熟悉置换群(或对称群)的人会知道，任何置换都有循环表示法。我想把X看作一个赋值函数，如下所示；

1->3

2->4

3->1

4->2

5->5

在某种程度上，如果上述函数是置换西格玛，那么我们有西格玛(1)=X中的第一个条目，西格玛(2)=X的第二个条目，依此类推

最后，我需要计算这个排列中有多少个循环，或者循环符号中的循环数。对于上面的例子，我们有

1->3-->1(所以这是一个单循环)

2-->4-->2(另一个循环)

5-->5(这也是一个循环)

所以它也应该告诉我，在这种情况下，X有3个循环。

这可能是一个详细的问题，但任何微小的帮助都是值得感激的。非常感谢大家！

Answer 1

整数数组已经是一个置换，只偏移一，因为C中的数组是零索引的。您可以在循环中迭代该数组/置换p；一旦您看到不属于任何已知循环的元素x，请连续计算p[x]、p[p[x]], ...，直到返回到x(在C代码中这样做时减去1，以说明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("%un", count_cycles(permutation, N)); // prints "3"
}