计算数组中的循环

Question

我必须编写一些代码来对数组中的循环进行计数。

我在谷歌找到了我认为是一个解决办法，用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 

到目前为止，我写了这个代码我自己，这是我尝试在Python代码转换成Java代码，它不起作用：

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); 
} 

我找到的Python代码返回每个循环中涉及的数字，但我真的只需要找到循环的数量。

如何正确地转换代码或想出另一个解决方案？

Answer 1

我想你想找到一个数组中存储的置换周期（也就是说，数组的值是索引0..N-1）。 对不对？

如果是这样的话，你需要做的就是从一个排列的阵列表示转换为图形/邻接矩阵表示，然后运行一个连接组件算法，如answer（也是python代码）所述。 连接组件的数量是周期数。