返回最长的连续整数序列
Returning longest consecutive sequence of ranging integers
问题
tl;dr - 下面的代码显示了我希望通过尝试某种不同的方法来改进的算法。
现在是长篇解释。
给定一个整数列表，我想找到与序列的原始起点相同或更高的每个连续整数序列。该序列也应该比排名更高的连续序列长。
你可能很困惑。让我来说明一下我的意思。
当我有一个整数列表时，我可以将它展开以表示它的范围。示例：
2,1,1,3,3,1
变成
-,-,-,3,3,-
2,-,-,2,2,-
1,1,1,1,1,1
如您所见，每个整数值都在其各自的行中，递减值填充其下方的列。请注意，上述过程不必在算法中执行。
我现在想 return 一个 level/row 上没有被另一个序列完全覆盖的每个序列。
例如，在这里，列表中没有 0，这意味着 ones 的基线具有最大长度。 returned 值之一现在是 [1, 6, 5]：1 表示序列包含的数字，6 表示序列的长度，5 表示序列的最终索引。
对于中间一排，我们只有两个。我们来分析一下。这里的第一个序列是开头的单二。它的 return 值为 [2,1,0]。然后是两个空格，之后是另外两个 2。可是等等！不要添加它们！二元组的顺序完全被上面的三元组覆盖了。所以实际上，我们在这一行中完成了。
在顶行，我们可以添加三的序列：[3,2,4]
现在的最终输出是
[[1,6,5],[2,1,0],[3,2,4]]
再举几个例子
为便于说明，这里有几个例子。它们是 100% 完整和正确的，我已经多次检查过它们。
[3,3,3,2,1] -> [[1,5,4],[2,4,3],[3,3,2]]
[7,7,3,0,1,2,3] -> [[1,3,6],[2,2,6],[3,3,2],[3,1,6],[7,2,1]]
[0,0,0] -> []
[0,1,0,4,0,1,0] -> [[1,1,1],[4,1,3],[1,1,5]]
到目前为止我的方法
我想到了一个比较复杂的方法，就是把列表中的值从出现次数最多的1次开始迭代。每当我遇到一个序列时，我都会保存它，然后将它的所有元素减1 .不过，在执行后者之前，我先检查序列的起始索引和结束索引左侧或右侧的值是否分别小于序列中的数字。例如，在以下情况下为真：
[2,4,4,4,1], looking at 3*4
[1,8,8], looking at 2*8
[9,9,9,8], looking at 3*9
[9,7,4], looking at 2*7 (sequence doesn't formally exist as [7,7],
but would be in the results, as described above)
如果是这样，那么我会递减序列的所有值以适应周围环境。
让我们 运行 使用一个简单的列表来完成该过程：
[4,4,2,1,1,3]
我们首先检查四肢。一开始就有两个，多方便啊！它左边没有值，它右边的值是 2 ...所以 1 小 2 点。所以......我们可以愉快地递减列表的所有元素。不过，在此之前，我们将序列 ([4,2,1]) 的值传递给一个变量。之后，我们读取周围最大的整数值，赋值给序列的所有元素，得到：
[2,2,2,1,1,3]
啊哈！现在它与右边的 2 持平。我们现在需要做的就是检查是否有值为 3 的整数。好吧，哇，角落里坐着一个小家伙。同样，我们保存序列 ([3,1,5]) 的值，并为每个元素分配最高的周围整数，恰好是 1:
[2,2,2,1,1,1]
又一次。我们 return [2,3,2].
[1,1,1,1,1,1]
怎么，这看起来是不是很眼熟。我们所要做的就是 return [1,6,5] 到这里就完成了。
最终输出为[[4,2,1],[3,1,5],[2,3,2],[1,6,5]].
懒得看更多的例子了...反正这个 post 太长了。
代码
是的，我已经有了一些代码。这是：
def ListProcessing(listL, length, freq):
#to detect end of array and not miss out on last sequences
listL.extend([0])
#Iterating over all unique elements that appear in the list from top to
#bottom, leaving out elements under or equal to _length_
for checkNum in reversed(list(set(sorted(listL))-set(range(length)))):
seqLen = 0
#Iterate over list
for index, val in enumerate(listL):
#current element higher than checkNum?
#Yes -> increase counter of the sequence length
if val >= checkNum:
seqLen += 1
#No -> Reset seqLen. If seqLen is high enough, replace sequence with
# sequence of highest neighbouring elements and yield the seq.
else:
if seqLen > freq-1:
newVal = max(val, listL[index-seqLen-1])
listL[index-seqLen:index] = [newVal] * seqLen
yield(checkNum, seqLen, index-1)
seqLen = 0
据我所知，它完全符合我的要求。
所以 - 问题是什么？
如上所述，我的算法已经有效。然而，这种方法似乎有点复杂，我相信有更好的方法。我很想听听另一种方法。
目前正致力于使用 array.array 模块来实现它以使其更快。如果有人想尝试用它实现自己的方法，我会非常兴奋。
欢迎未实现的concepts/ideas！
这是一个有趣的问题，这是解决它的另一种方法。让我们举个例子，seq = [4, 4, 2, 1, 1, 3, 2]。请注意，我们可以首先返回与遵循您问题中规定的规则的最长可能序列相关联的结果。该结果将具有 [min(seq), len(seq), len(seq) - 1] 或 [1, 7, 6].
的形式
现在您知道所有其他有效结果只能包含大于 min(seq) 的值，因此我们可以将 seq 拆分为两个子序列，[4, 4, 2] 和 [3, 2]并在这些子序列中寻找有效结果。我们可以对每个子序列递归地重复这个分裂过程，直到我们没有子序列。
在看起来像这样的代码中：
def recListProcessing(seq, threshold=0, min_len=1):
len_seq = len(seq)
if len_seq < min_len:
return
min_value = min(seq)
if min_value > threshold:
yield (min_value, len_seq, len_seq - 1)
start = 0
while start < len_seq:
try:
end = seq.index(min_value, start)
except ValueError:
end = len_seq
sub_seq = seq[start:end]
for item in recListProcessing(sub_seq, threshold, min_len):
yield (item[0], item[1], item[2] + start)
start = end + 1
问题
tl;dr - 下面的代码显示了我希望通过尝试某种不同的方法来改进的算法。
现在是长篇解释。
给定一个整数列表，我想找到与序列的原始起点相同或更高的每个连续整数序列。该序列也应该比排名更高的连续序列长。
你可能很困惑。让我来说明一下我的意思。
当我有一个整数列表时，我可以将它展开以表示它的范围。示例：
2,1,1,3,3,1
变成
-,-,-,3,3,-
2,-,-,2,2,-
1,1,1,1,1,1
如您所见，每个整数值都在其各自的行中，递减值填充其下方的列。请注意，上述过程不必在算法中执行。
我现在想 return 一个 level/row 上没有被另一个序列完全覆盖的每个序列。
例如，在这里，列表中没有 0，这意味着 ones 的基线具有最大长度。 returned 值之一现在是 [1, 6, 5]：1 表示序列包含的数字，6 表示序列的长度，5 表示序列的最终索引。
对于中间一排，我们只有两个。我们来分析一下。这里的第一个序列是开头的单二。它的 return 值为 [2,1,0]。然后是两个空格，之后是另外两个 2。可是等等！不要添加它们！二元组的顺序完全被上面的三元组覆盖了。所以实际上，我们在这一行中完成了。
在顶行，我们可以添加三的序列：[3,2,4]
现在的最终输出是
[[1,6,5],[2,1,0],[3,2,4]]
再举几个例子
为便于说明，这里有几个例子。它们是 100% 完整和正确的，我已经多次检查过它们。
[3,3,3,2,1] -> [[1,5,4],[2,4,3],[3,3,2]]
[7,7,3,0,1,2,3] -> [[1,3,6],[2,2,6],[3,3,2],[3,1,6],[7,2,1]]
[0,0,0] -> []
[0,1,0,4,0,1,0] -> [[1,1,1],[4,1,3],[1,1,5]]
到目前为止我的方法
我想到了一个比较复杂的方法，就是把列表中的值从出现次数最多的1次开始迭代。每当我遇到一个序列时，我都会保存它，然后将它的所有元素减1 .不过，在执行后者之前，我先检查序列的起始索引和结束索引左侧或右侧的值是否分别小于序列中的数字。例如，在以下情况下为真：
[2,4,4,4,1], looking at 3*4
[1,8,8], looking at 2*8
[9,9,9,8], looking at 3*9
[9,7,4], looking at 2*7 (sequence doesn't formally exist as [7,7],
but would be in the results, as described above)
如果是这样，那么我会递减序列的所有值以适应周围环境。
让我们 运行 使用一个简单的列表来完成该过程：
[4,4,2,1,1,3]
我们首先检查四肢。一开始就有两个，多方便啊！它左边没有值，它右边的值是 2 ...所以 1 小 2 点。所以......我们可以愉快地递减列表的所有元素。不过，在此之前，我们将序列 ([4,2,1]) 的值传递给一个变量。之后，我们读取周围最大的整数值，赋值给序列的所有元素，得到：
[2,2,2,1,1,3]
啊哈！现在它与右边的 2 持平。我们现在需要做的就是检查是否有值为 3 的整数。好吧，哇，角落里坐着一个小家伙。同样，我们保存序列 ([3,1,5]) 的值，并为每个元素分配最高的周围整数，恰好是 1:
[2,2,2,1,1,1]
又一次。我们 return [2,3,2].
[1,1,1,1,1,1]
怎么，这看起来是不是很眼熟。我们所要做的就是 return [1,6,5] 到这里就完成了。
最终输出为[[4,2,1],[3,1,5],[2,3,2],[1,6,5]].
懒得看更多的例子了...反正这个 post 太长了。
代码
是的，我已经有了一些代码。这是：
def ListProcessing(listL, length, freq):
#to detect end of array and not miss out on last sequences
listL.extend([0])
#Iterating over all unique elements that appear in the list from top to
#bottom, leaving out elements under or equal to _length_
for checkNum in reversed(list(set(sorted(listL))-set(range(length)))):
seqLen = 0
#Iterate over list
for index, val in enumerate(listL):
#current element higher than checkNum?
#Yes -> increase counter of the sequence length
if val >= checkNum:
seqLen += 1
#No -> Reset seqLen. If seqLen is high enough, replace sequence with
# sequence of highest neighbouring elements and yield the seq.
else:
if seqLen > freq-1:
newVal = max(val, listL[index-seqLen-1])
listL[index-seqLen:index] = [newVal] * seqLen
yield(checkNum, seqLen, index-1)
seqLen = 0
据我所知，它完全符合我的要求。
所以 - 问题是什么？
如上所述，我的算法已经有效。然而，这种方法似乎有点复杂，我相信有更好的方法。我很想听听另一种方法。
目前正致力于使用 array.array 模块来实现它以使其更快。如果有人想尝试用它实现自己的方法，我会非常兴奋。
欢迎未实现的concepts/ideas！
这是一个有趣的问题，这是解决它的另一种方法。让我们举个例子，seq = [4, 4, 2, 1, 1, 3, 2]。请注意，我们可以首先返回与遵循您问题中规定的规则的最长可能序列相关联的结果。该结果将具有 [min(seq), len(seq), len(seq) - 1] 或 [1, 7, 6].
现在您知道所有其他有效结果只能包含大于 min(seq) 的值，因此我们可以将 seq 拆分为两个子序列，[4, 4, 2] 和 [3, 2]并在这些子序列中寻找有效结果。我们可以对每个子序列递归地重复这个分裂过程，直到我们没有子序列。
在看起来像这样的代码中：
def recListProcessing(seq, threshold=0, min_len=1):
len_seq = len(seq)
if len_seq < min_len:
return
min_value = min(seq)
if min_value > threshold:
yield (min_value, len_seq, len_seq - 1)
start = 0
while start < len_seq:
try:
end = seq.index(min_value, start)
except ValueError:
end = len_seq
sub_seq = seq[start:end]
for item in recListProcessing(sub_seq, threshold, min_len):
yield (item[0], item[1], item[2] + start)
start = end + 1