How to turn an array of integers into a permutation and count the loops in it?

Question

I have been checking it over the net and asking friends, since I am very new to coding. I find all these posts about writing all possible permutations on n letters. I am not looking for that.

What I am trying to achieve is given an array of integers, I want to turn that into a permutation as follows. Say X is an array of integers;

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

Now people familiar with permutation groups (or symmetric group) would know that there is cycle notation for any permutation. I want to see X as some function that assigns values as follow;

1 --> 3

2 --> 4

3 --> 1

4 --> 2

5 --> 5

In a way, if the above function is the permutation sigma, then we have sigma(1)= 1st entry in X, sigma(2)= 2nd entry in X and so on.

And finally, I need to count how many loops there will be in this permutation, or number of cycles in a cycle notation. Again for the example above, we have

1 --> 3 --> 1 (So this is a one loop)

2 --> 4 --> 2 (Another loop)

5 --> 5 (This is also a loop)

So it should also tell me that X has 3 loops in this case.

This might be a detailed question, but any any, tiny bit of help is appreciated. Thank you all sooo much!

I changed the title, I hope it is more appropriate now. Thanks for your quick response, since I am a complete newbie, the post you referred me to talks about a python code. I want to do this in C, do you think a similar approach would work in C as well? — Hakan Doga, Dec 28 '18 at 09:05

kfx · Accepted Answer · 2018-12-28T09:14:24.363

The array of integers already is a permutation, only offset by one, since arrays in C are zero-indexed. You can iterate through that array/permutation p in a loop; once you see an element x that does not belong to any known cycle, continuously calculate p[x], p[p[x]], ... until you get back to x (subtract 1 when doing that in the C code to account for the zero indexing of C arrays). That is one cycle; account for this cycle and proceed to the next element. C code is presented below.

Another way is to convert the permutation to a graph and count the number of connected components in the graph, as done here.

#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"
}

Thanks a lot @kfx ! I never thought about the graph idea, which is brilliant! The code above is great, but I will also try and understand the graph one. — Hakan Doga, Dec 28 '18 at 09:17

How to turn an array of integers into a permutation and count the loops in it?

1 Answers1