如何确定列表中的循环？
How to determine cycles in a list?
考虑一个整数索引列表，indices。 indices 的所有元素都在列表 indices 的范围内。列表 indices 中的所有值都是唯一的。示例 [2, 0, 1, 4, 3, 5].
给定一个索引（例如 0），继续 indices[0]（即上例中的 2）。重复可以无限期地完成。当移动 returns 到一个已经访问过的索引时，会发生一个循环。总是至少有一个循环。循环长度的总和等于列表的长度indices。
我需要创建一个函数 cycles(indices) returns 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
我的代码的问题是，如果它已经通过了较小循环的元素，它不会重新检查较大循环的元素中是否有较小的循环。关于如何解决这个编码问题有什么建议吗？
请注意，我刚刚开始学习如何编程，并且正在学习入门在线课程，因此我希望能提供简单的解决方案。
一个粗略的解决方案，使用集合来跟踪我们已经访问过的索引：
def cycles(indices):
def get_loop(indices, idx): # this funtion returns a loop, starting from index `idx`
seen, loop = set(), []
while True:
v = indices[idx] # get index on position `idx`
if v not in seen: # have we seen index `v` already?
loop.append(idx) # no, add it as part of the loop
seen.add(v) # update set `seen` with index `v`
idx = v # set current index `idx` with index `v`
else:
break # yes, that means we closed the loop
return loop # return this loop
rv, seen = [], set()
for i in indices: # iterate over all indices
if i not in seen: # is index `i` part of any loop we already have?
loop = get_loop(indices, i) # no, so call get_loop() with starting index `i`
rv.append(loop) # we add this loop to the result list
seen.update(loop) # update set `seen` with all indices inside this loop
return rv
print(cycles([2, 0, 1, 4, 3, 5]))
print(cycles([0, 1, 2, 3, 4, 5]))
print(cycles([12, 0, 8, 10, 9, 6, 5, 4, 13, 7, 17,14, 2,18, 16, 1, 11, 19, 3, 15]))
打印：
[[2, 1, 0], [4, 3], [5]]
[[0], [1], [2], [3], [4], [5]]
[[12, 2, 8, 13, 18, 3, 10, 17, 19, 15, 1, 0], [9, 7, 4], [6, 5], [14, 16, 11]]
如果索引已经是循环的一部分，您可以跳过它。
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]]
您可以跟踪您已经访问过的所有索引，并在下次忽略它们。此外，每个循环都有唯一的索引，无论您在循环中的何处开始（12 或 0，如果两者在同一循环中），您始终可以完成循环（如圆圈）。
def gen_cycles(indices):
cycles = []
visited = []
for i in indices:
if(i in visited):
continue
start = i;
current_cycle = []
current_cycle.append(start)
visited.append(start)
j = indices[start]
while(j!=start):
current_cycle.append(j)
visited.append(j)
j = indices[j]
cycles.append(current_cycle)
return cycles
print(gen_cycles([12, 0, 8, 10, 9, 6, 5, 4, 13, 7, 17,14, 2,18, 16, 1, 11, 19, 3, 15]))
Output: [[12, 2, 8, 13, 18, 3, 10, 17, 19, 15, 1, 0], [9, 7, 4], [6, 5], [14, 16, 11]]
让我们看看[2, 0, 1, 4, 3, 5]。在循环[2, 0, 1]中，数字的顺序并不重要，所以如果你从它的任何一点开始，你就会得到正确的循环。
对于大小为 N 的数组，一个简单的解决方案是：
1. 遍历所有索引 1..N-1 作为 starting_index
2. 获取从索引 starting_index 开始的循环
3. 如果我们已经看到这个循环，则丢弃它。否则记住了。
函数可能如下所示：
def get_cycles(array):
cycles = []
for starting_index in range(len(array)):
cycle = cycle_at(array, starting_index)
if not any(are_equal(existing, cycle) for existing in cycles):
cycles.append(cycle)
return cycles
如果您不熟悉 any，带有 any 的行大致如下：
def any(iterable):
for x in iterable:
if x:
return True
return False
我们希望循环 [0, 1, 2] 和 [1, 2, 0] 被认为是相等的。
我们可以编写一个函数来移动其中一个，直到它匹配第二个：
def are_equal(cycle1, cycle2):
if len(cycle1) != len(cycle2):
return False
for i in range(len(cycle1)):
# [1, 2, 3, 4] -> [2, 3, 4, 1]
cycle1 = cycle1[1:] + [cycle1[0]]
if cycle1 == cycle2:
return True
return False
或者我们可以使用这些循环的属性并得到：
def are_equal(cycle1, cycle2):
return set(cycle1) == set(cycle2)
因为两个循环相等当且仅当它们包含相同的元素（顺序无关紧要——正如声明所说）。
然后我们需要实现一个函数，使循环从索引 i 开始。
def cycle_at(array, index):
visited_indices = set()
cycle = []
while True:
cycle.append(index)
visited_indices.add(index)
index = array[index]
if index in visited_indices:
break
return cycle
我们需要记住我们访问了哪些索引，我们会将它们存储在一个集合中。
然后我们将 'follow the cycle' 并遍历数组，每次看到新索引时将 index 添加到 visited_indices。
如果在任何时候我们偶然发现了我们已经访问过的索引，我们将结束循环。
您可以通过不考虑循环中已经出现的索引作为起始索引来提高性能，因为这将消除对 are_equal 函数的需要，并且会阻止您找到相同的循环超过一次。
你可以试试这个。
def cycles(indices):
sub =[]
i=0
result = []
remaining = indices[:]
while remaining:
i = indices[i]
if(i in sub):
remaining = [ a for a in remaining if a not in sub]
result.append(sub)
sub = []
if remaining:
i=remaining[0]
sub.append(i)
return result
r = cycles([2, 0, 1, 4, 3, 5])
print(r)
#[[2, 1, 0], [4, 3], [5]]
r = cycles([0,1,2,3,4,5])
print(r)
#[[0], [1], [2], [3], [4], [5]]
这看起来是一个完美的图论问题。您可以将列表中的元素连接到它们的索引，并在结果图中查找连接的组件。 networkx 是最流行的 Python 网络分析包：
import networkx as nx
lst = [2, 0, 1, 4, 3, 5]
G = nx.Graph()
G.add_edges_from(enumerate(lst))
print(list(nx.connected_components(G)))
# [{0, 1, 2}, {3, 4}, {5}]
def find_cycles(indices):
indices = indices.copy()
cycles = list()
for a in indices:
if a is None: continue
cycle = list()
while a is not None:
cycle.append(a)
indices[a], a = None, indices[a]
else: cycles.append(cycle[:-1])
return cycles
print(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]]
但如果你不需要之后的输入，你可以删除indices = indices.copy()。
考虑一个整数索引列表，indices。 indices 的所有元素都在列表 indices 的范围内。列表 indices 中的所有值都是唯一的。示例 [2, 0, 1, 4, 3, 5].
给定一个索引（例如 0），继续 indices[0]（即上例中的 2）。重复可以无限期地完成。当移动 returns 到一个已经访问过的索引时，会发生一个循环。总是至少有一个循环。循环长度的总和等于列表的长度indices。
我需要创建一个函数 cycles(indices) returns 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
我的代码的问题是，如果它已经通过了较小循环的元素，它不会重新检查较大循环的元素中是否有较小的循环。关于如何解决这个编码问题有什么建议吗？
请注意，我刚刚开始学习如何编程，并且正在学习入门在线课程，因此我希望能提供简单的解决方案。
一个粗略的解决方案，使用集合来跟踪我们已经访问过的索引：
def cycles(indices):
def get_loop(indices, idx): # this funtion returns a loop, starting from index `idx`
seen, loop = set(), []
while True:
v = indices[idx] # get index on position `idx`
if v not in seen: # have we seen index `v` already?
loop.append(idx) # no, add it as part of the loop
seen.add(v) # update set `seen` with index `v`
idx = v # set current index `idx` with index `v`
else:
break # yes, that means we closed the loop
return loop # return this loop
rv, seen = [], set()
for i in indices: # iterate over all indices
if i not in seen: # is index `i` part of any loop we already have?
loop = get_loop(indices, i) # no, so call get_loop() with starting index `i`
rv.append(loop) # we add this loop to the result list
seen.update(loop) # update set `seen` with all indices inside this loop
return rv
print(cycles([2, 0, 1, 4, 3, 5]))
print(cycles([0, 1, 2, 3, 4, 5]))
print(cycles([12, 0, 8, 10, 9, 6, 5, 4, 13, 7, 17,14, 2,18, 16, 1, 11, 19, 3, 15]))
打印：
[[2, 1, 0], [4, 3], [5]]
[[0], [1], [2], [3], [4], [5]]
[[12, 2, 8, 13, 18, 3, 10, 17, 19, 15, 1, 0], [9, 7, 4], [6, 5], [14, 16, 11]]
如果索引已经是循环的一部分，您可以跳过它。
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]]
您可以跟踪您已经访问过的所有索引，并在下次忽略它们。此外，每个循环都有唯一的索引，无论您在循环中的何处开始（12 或 0，如果两者在同一循环中），您始终可以完成循环（如圆圈）。
def gen_cycles(indices):
cycles = []
visited = []
for i in indices:
if(i in visited):
continue
start = i;
current_cycle = []
current_cycle.append(start)
visited.append(start)
j = indices[start]
while(j!=start):
current_cycle.append(j)
visited.append(j)
j = indices[j]
cycles.append(current_cycle)
return cycles
print(gen_cycles([12, 0, 8, 10, 9, 6, 5, 4, 13, 7, 17,14, 2,18, 16, 1, 11, 19, 3, 15]))
Output: [[12, 2, 8, 13, 18, 3, 10, 17, 19, 15, 1, 0], [9, 7, 4], [6, 5], [14, 16, 11]]
让我们看看[2, 0, 1, 4, 3, 5]。在循环[2, 0, 1]中，数字的顺序并不重要，所以如果你从它的任何一点开始，你就会得到正确的循环。
对于大小为 N 的数组，一个简单的解决方案是：
1. 遍历所有索引 1..N-1 作为 starting_index
2. 获取从索引 starting_index 开始的循环
3. 如果我们已经看到这个循环，则丢弃它。否则记住了。
函数可能如下所示：
def get_cycles(array):
cycles = []
for starting_index in range(len(array)):
cycle = cycle_at(array, starting_index)
if not any(are_equal(existing, cycle) for existing in cycles):
cycles.append(cycle)
return cycles
如果您不熟悉 any，带有 any 的行大致如下：
def any(iterable):
for x in iterable:
if x:
return True
return False
我们希望循环 [0, 1, 2] 和 [1, 2, 0] 被认为是相等的。
我们可以编写一个函数来移动其中一个，直到它匹配第二个：
def are_equal(cycle1, cycle2):
if len(cycle1) != len(cycle2):
return False
for i in range(len(cycle1)):
# [1, 2, 3, 4] -> [2, 3, 4, 1]
cycle1 = cycle1[1:] + [cycle1[0]]
if cycle1 == cycle2:
return True
return False
或者我们可以使用这些循环的属性并得到：
def are_equal(cycle1, cycle2):
return set(cycle1) == set(cycle2)
因为两个循环相等当且仅当它们包含相同的元素（顺序无关紧要——正如声明所说）。
然后我们需要实现一个函数，使循环从索引 i 开始。
def cycle_at(array, index):
visited_indices = set()
cycle = []
while True:
cycle.append(index)
visited_indices.add(index)
index = array[index]
if index in visited_indices:
break
return cycle
我们需要记住我们访问了哪些索引，我们会将它们存储在一个集合中。
然后我们将 'follow the cycle' 并遍历数组，每次看到新索引时将 index 添加到 visited_indices。
如果在任何时候我们偶然发现了我们已经访问过的索引，我们将结束循环。
您可以通过不考虑循环中已经出现的索引作为起始索引来提高性能，因为这将消除对 are_equal 函数的需要，并且会阻止您找到相同的循环超过一次。
你可以试试这个。
def cycles(indices):
sub =[]
i=0
result = []
remaining = indices[:]
while remaining:
i = indices[i]
if(i in sub):
remaining = [ a for a in remaining if a not in sub]
result.append(sub)
sub = []
if remaining:
i=remaining[0]
sub.append(i)
return result
r = cycles([2, 0, 1, 4, 3, 5])
print(r)
#[[2, 1, 0], [4, 3], [5]]
r = cycles([0,1,2,3,4,5])
print(r)
#[[0], [1], [2], [3], [4], [5]]
这看起来是一个完美的图论问题。您可以将列表中的元素连接到它们的索引，并在结果图中查找连接的组件。 networkx 是最流行的 Python 网络分析包：
import networkx as nx
lst = [2, 0, 1, 4, 3, 5]
G = nx.Graph()
G.add_edges_from(enumerate(lst))
print(list(nx.connected_components(G)))
# [{0, 1, 2}, {3, 4}, {5}]
def find_cycles(indices):
indices = indices.copy()
cycles = list()
for a in indices:
if a is None: continue
cycle = list()
while a is not None:
cycle.append(a)
indices[a], a = None, indices[a]
else: cycles.append(cycle[:-1])
return cycles
print(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]]
但如果你不需要之后的输入，你可以删除indices = indices.copy()。