Counting cycles in a permutation of an array

Question

I have to write some code to count cycles in a permutation of an array.

I've found on Google what I think is a solution, written in python:

def key(element):
return element

def find_cycles(l):
seen = set()
cycles = []
for i in range(len(l)):
    if i != key(l[i]) and not i in seen:
        cycle = []
        n = i
        while 1: 
            cycle.append(n)
            n = key(l[n])
            if n == i:
                break
        seen = seen.union(set(cycle))
        cycles.append(list(reversed(cycle)))
return cycles

So far I wrote this code myself, which is my attempt to convert the Python code into Java code and it doesn't work:

    public static ArrayList<Integer> numbers;
public static ArrayList<Integer> cycles;
public static ArrayList<Integer> cycle; 

public Puslespil(int permutations){
    numbers = new ArrayList<Integer>(); 
    for (int i = 0; i<permutations;i++){
        numbers.add(i);
    }
}

public static void main(String[] args){
    new Puslespil(5);
    ArrayList<Integer> visited = new ArrayList<Integer>();
    cycles = new ArrayList<Integer>();
    Collections.shuffle(numbers);
    System.out.println(numbers);
    for(int i=0; i<numbers.size();i++){
        if(i != numbers.get(i) && !visited.contains(i)){
            cycle = new ArrayList<Integer>();

        }
        int n = i;
        while(true){
            cycle.add(n);
            n = numbers.get(n);
            if(n == i)
                break;
            visited.addAll(cycle);
            Collections.reverse(cycle);
            cycles.addAll(cycle);

        }

    }

    System.out.println("cycles: " + cycles);
}

The Python code I found returns the numbers involved in each cycle, but I really only need to find the amount of cycles.

How can I convert the code properly, or come up with another solution?

score 0 · Answer 1 · edited May 23 '17 at 10:28

I think you want to find the cycles of a permutation stored in an array (that is, the values of the array are the indices 0..N-1). Right?

If that is the case, all you need to do is convert from an array representation of the permutation to a graph/adjacency matrix representation and then run a connected component algorithm as described in this answer (also python code). The number of connected components is the number of cycles.

Counting cycles in a permutation of an array

1 Answers1