python - 如何确定列表中的循环？

Question

考虑一个整数索引列表，indices。 indices 的所有元素都在列表 indices 的范围内。 indices 列表中的所有值都是唯一的。示例[2, 0, 1, 4, 3, 5]。

给定一个索引(例如 0)，转到 indices[0](即上例中的 2)。如此重复可以无限期地进行。当移动返回到已访问过的索引时，就会发生循环。总是至少有一个周期。循环长度的总和等于列表索引的长度。

我需要创建一个函数cycles(indices)，它返回indices中所有周期的列表。

对于上面的示例，预期输出列表为 [[2, 0, 1], [4, 3], [5]]。

对于列表[0, 1, 2, 3]，循环很简单，其形式为[[0], [1], [2], [3] ]。

注意:输出周期的顺序和索引的顺序并不重要。例如:[[2, 0, 1], [4, 3], [5]]相当于[[3, 4], [0, 1, 2], [5]]

这是我迄今为止想到的代码:

def cycles(indices):
    cycles = []
    old_i = []
    i = 0
    while i in range(len(indices)):
        old_i.append(i)
        i = indices[i]
        if i in old_i:
            cycles.append(old_i)
            i = max(old_i) + 1
            old_i = []

    return cycles

我的代码的问题是，如果它已经通过了较小循环的元素，它不会重新检查较大循环的元素中是否存在较小的循环。关于如何解决这个编码问题有什么建议吗？

请注意，我刚刚开始学习如何编程，并且正在学习在线入门类(class)，因此我希望获得简单的解决方案。

Answer 1

如果索引已经是循环的一部分，您可以跳过它。

def find_cycles(indices):
    """Given a list of indices return a list of cycles."""

    visited = set()
    cycles = []

    for start_ind in indices:

        if start_ind in visited:
            continue

        path = [start_ind]
        next_ind = indices[start_ind]

        while start_ind != next_ind:
            path.append(next_ind)
            next_ind = indices[next_ind]
        else:
            cycles.append(path)
            visited |= set(path)
    return cycles

find_cycles([12, 0, 8, 10, 9, 6, 5, 4, 13, 7, 17,14, 2,18, 16, 1, 11, 19, 3, 15])
# [[12, 2, 8, 13, 18, 3, 10, 17, 19, 15, 1, 0], [9, 7, 4], [6, 5], [14, 16, 11]]