找到一段最终周期序列
Find a period of eventually periodic sequence
简短说明。
我有一个数字序列 [0, 1, 4, 0, 0, 1, 1, 2, 3, 7, 0, 0, 1, 1, 2, 3, 7, 0, 0, 1, 1, 2, 3, 7, 0, 0, 1, 1, 2, 3, 7]。如您所见，从第 3 个值开始，序列是周期性的，周期为 [0, 0, 1, 1, 2, 3, 7].
我正在尝试从这个序列中自动提取这段时间。问题是我既不知道周期的长度，也不知道序列从哪个位置开始周期。
完整解释（可能需要一些数学知识）
我正在学习组合博弈论，这个理论的基石需要一个计算Grundy values of a game graph. This produces infinite sequence, which in many cases becomes eventually periodic。
我找到了一种有效计算粗糙值的方法（它 returns 我是一个序列）。我想自动提取此序列的偏移量和周期。我知道看到序列的一部分 [1, 2, 3, 1, 2, 3] 你不能确定 [1, 2, 3] 是一个句点（谁知道下一个数字可能是 4，这打破了假设） ，但我对这种复杂性不感兴趣（我假设序列足以找到真实周期）。另外问题是序列可以在期间的中间停止：[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, ...]（期间仍然是 1, 2, 3）。
我还需要找到最小的偏移量和周期。例如对于原始序列，偏移量可以是[0, 1, 4, 0, 0]和周期[1, 1, 2, 3, 7, 0, 0]，但最小的是[0, 1, 4]和[0, 0, 1, 1, 2, 3, 7]。
我的低效方法是尝试每一个可能的偏移量和每一个可能的周期。使用此数据构建序列并检查它是否与原始序列相同。我没有做任何正常的分析，但看起来它至少在时间复杂度上是二次的。
这是我的快速 python 代码（尚未正确测试）：
def getPeriod(arr):
min_offset, min_period, n = len(arr), len(arr), len(arr)
best_offset, best_period = [], []
for offset in xrange(n):
start = arr[:offset]
for period_len in xrange(1, (n - offset) / 2):
period = arr[offset: offset+period_len]
attempt = (start + period * (n / period_len + 1))[:n]
if attempt == arr:
if period_len < min_period:
best_offset, best_period = start[::], period[::]
min_offset, min_period = len(start), period_len
elif period_len == min_period and len(start) < min_offset:
best_offset, best_period = start[::], period[::]
min_offset, min_period = len(start), period_len
return best_offset, best_period
哪个 returns 我想要我的原始序列：
offset [0, 1, 4]
period [0, 0, 1, 1, 2, 3, 7]
还有什么更高效的吗？
我将从构建序列中值的直方图开始
所以你只需列出所有按顺序使用的数字（或其中的重要部分）并计算它们的出现次数。这是 O(n)，其中 n 是序列大小。
对直方图进行升序排序
这是 O(m.log(m))，其中 m 是不同值的数量。您还可以忽略最有可能在偏移中的低概率数字 (count<treshold)，或者只是进一步降低 m 的不规则性。对于周期性序列 m <<< n，因此无论序列是否周期性，您都可以将其用作第一个标记。
找出经期
在 直方图 中，counts 应该是 n/period 的倍数。所以直方图的approximate/findGCD算了。问题是您需要考虑计数和 n（偏移部分）中存在的不规则性，因此您需要大约计算 GCD。例如：
sequence = { 1,1,2,3,3,1,2,3,3,1,2,3,3 }
已排序直方图：
item,count
2 3
1 4
3 6
GCD(6,4)=2 和 GCD(6,3)=3 你应该至少检查 +/-1 GCD 结果，这样可能的周期是：
T = ~n/2 = 13/2 = 6
T = ~n/3 = 13/3 = 4
所以检查 T={3,4,5,6,7} 只是为了确定。在最高计数与最低计数之间始终使用 GCD。如果序列有很多不同的数字，你也可以做一个计数直方图，只检查最常见的值。
要检查周期有效性，只需取序列末尾或中间的任何项目（只需使用可能的周期区域）。然后在它发生之前（或之后）的可能时期附近的附近区域寻找它。如果找到几次你就得到了正确的时期（或其倍数）
获取准确的周期
只需检查找到的周期分数 (T/2, T/3, ...) 或对找到的周期做一个直方图，最小的 count 告诉您封装了多少个实际周期，所以除以它.
查找偏移量
当您知道经期时，这很容易。只需从头开始扫描第一项，然后查看经期后是否再次出现。如果不记得位置。在序列的末尾或中间停止……或在某些门槛上取得成功。这最多 O(n) 最后记住的位置是 offset 中的最后一项。
[edit1] 很好奇所以我尝试用 C++ 编写代码
我 simplified/skip 一些东西（假设至少有一半的数组是周期性的）来测试我是否在我的算法中没有犯一些愚蠢的错误，这里的结果（按预期工作）：
const int p=10; // min periods for testing
const int n=500; // generated sequence size
int seq[n]; // generated sequence
int offset,period; // generated properties
int i,j,k,e,t0,T;
int hval[n],hcnt[n],hs; // histogram
// generate periodic sequence
Randomize();
offset=Random(n/5);
period=5+Random(n/5);
for (i=0;i<offset+period;i++) seq[i]=Random(n);
for (i=offset,j=i+period;j<n;i++,j++) seq[j]=seq[i];
if ((offset)&&(seq[offset-1]==seq[offset-1+period])) seq[offset-1]++;
// compute histogram O(n) on last half of it
for (hs=0,i=n>>1;i<n;i++)
{
for (e=seq[i],j=0;j<hs;j++)
if (hval[j]==e) { hcnt[j]++; j=-1; break; }
if (j>=0) { hval[hs]=e; hcnt[hs]=1; hs++; }
}
// bubble sort histogram asc O(m^2)
for (e=1,j=hs;e;j--)
for (e=0,i=1;i<j;i++)
if (hcnt[i-1]>hcnt[i])
{ e=hval[i-1]; hval[i-1]=hval[i]; hval[i]=e;
e=hcnt[i-1]; hcnt[i-1]=hcnt[i]; hcnt[i]=e; e=1; }
// test possible periods
for (j=0;j<hs;j++)
if ((!j)||(hcnt[j]!=hcnt[j-1])) // distinct counts only
if (hcnt[j]>1) // more then 1 occurence
for (T=(n>>1)/(hcnt[j]+1);T<=(n>>1)/(hcnt[j]-1);T++)
{
for (i=n-1,e=seq[i],i-=T,k=0;(i>=(n>>1))&&(k<p)&&(e==seq[i]);i-=T,k++);
if ((k>=p)||(i<n>>1)) { j=hs; break; }
}
// compute histogram O(T) on last multiple of period
for (hs=0,i=n-T;i<n;i++)
{
for (e=seq[i],j=0;j<hs;j++)
if (hval[j]==e) { hcnt[j]++; j=-1; break; }
if (j>=0) { hval[hs]=e; hcnt[hs]=1; hs++; }
}
// least count is the period multiple O(m)
for (e=hcnt[0],i=0;i<hs;i++) if (e>hcnt[i]) e=hcnt[i];
if (e) T/=e;
// check/handle error
if (T!=period)
{
return;
}
// search offset size O(n)
for (t0=-1,i=0;i<n-T;i++)
if (seq[i]!=seq[i+T]) t0=i;
t0++;
// check/handle error
if (t0!=offset)
{
return;
}
代码仍未优化。对于 n=10000，我的设置大约需要 5ms。结果在 t0（偏移量）和 T（句点）中。 您可能需要稍微调整一下阈值常量
备注:如果有句点P1长度为 L，那么还有一段P2，长度相同，L，使得输入序列恰好以 P2 结束（ 即 我们没有在末尾涉及部分周期）。
的确，通过改变offset总能得到相同长度的不同周期。新周期将是初始周期的轮换。
例如，以下序列的周期长度为 4，偏移量为 3：
0 0 0 (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2
但它也有一个长度相同且偏移量为 5 的句点，末尾没有部分句点：
0 0 0 1 2 (3 4 1 2) (3 4 1 2) (3 4 1 2) (3 4 1 2) (3 4 1 2)
言下之意，我们可以通过逆序处理序列，从末尾开始使用零偏移量来查找最小周期，从而找到周期的最小长度。一种可能的方法是简单地在反向列表上使用您当前的算法，而不需要对偏移量进行循环。
既然我们知道了所需周期的长度，我们也可以找到它的最小偏移量。一种可能的方法是尝试所有不同的偏移量（优点是不需要循环长度，因为长度是已知的），但是，如果需要，可以进一步优化，例如通过推进尽可能多地从末尾处理列表，允许周期的最终重复（即最接近未反转序列开始的那个）是部分的。
我不得不做一次类似的事情。我使用了蛮力和一些常识，解决方案不是很优雅，但它有效。该解决方案始终有效，但您必须在函数中设置正确的参数 (k,j, con)。
- 序列在变量seq.
中保存为列表
- k 是序列数组的大小，如果你认为你的序列需要很长时间才能变成周期性的，那么将这个 k 设置为一个很大的数字。
- 变量 found 会告诉我们数组是否通过周期测试 j
- j是周期
- 如果您期望一个大周期，那么您必须将 j 设置为一个大数字。
- 我们通过检查序列的最后 j+30 个数字来测试周期性。
- 周期越大(j)越需要检查
- 一旦其中一个测试通过，我们就退出该函数，我们 return 较小的周期。
您可能会注意到准确性取决于变量 j 和 k 但如果您将它们设置为非常大的数字，它总是正确。
def some_sequence(s0, a, b, m):
try:
seq=[s0]
snext=s0
findseq=True
k=0
while findseq:
snext= (a*snext+b)%m
seq.append(snext)
#UNTIL THIS PART IS JUST TO CREATE THE SEQUENCE (seq) SO IS NOT IMPORTANT
k=k+1
if k>20000:
# I IS OUR LIST INDEX
for i in range(1,len(seq)):
for j in range(1,1000):
found =True
for con in range(j+30):
#THE TRICK IS TO START FROM BEHIND
if not (seq[-i-con]==seq[-i-j-con]):
found = False
if found:
minT=j
findseq=False
return minT
except:
return None
简化版
def get_min_period(sequence,max_period,test_numb):
seq=sequence
if max_period+test_numb > len(sequence):
print("max_period+test_numb cannot be bigger than the seq length")
return 1
for i in range(1,len(seq)):
for j in range(1,max_period):
found =True
for con in range(j+test_numb):
if not (seq[-i-con]==seq[-i-j-con]):
found = False
if found:
minT=j
return minT
其中 max_period 是您要查找的最大周期，test_numb 是多少您要测试的序列号，越大越好，但您必须 max_period+test_numb < len(sequence)
简短说明。
我有一个数字序列 [0, 1, 4, 0, 0, 1, 1, 2, 3, 7, 0, 0, 1, 1, 2, 3, 7, 0, 0, 1, 1, 2, 3, 7, 0, 0, 1, 1, 2, 3, 7]。如您所见，从第 3 个值开始，序列是周期性的，周期为 [0, 0, 1, 1, 2, 3, 7].
我正在尝试从这个序列中自动提取这段时间。问题是我既不知道周期的长度，也不知道序列从哪个位置开始周期。
完整解释（可能需要一些数学知识）
我正在学习组合博弈论，这个理论的基石需要一个计算Grundy values of a game graph. This produces infinite sequence, which in many cases becomes eventually periodic。
我找到了一种有效计算粗糙值的方法（它 returns 我是一个序列）。我想自动提取此序列的偏移量和周期。我知道看到序列的一部分 [1, 2, 3, 1, 2, 3] 你不能确定 [1, 2, 3] 是一个句点（谁知道下一个数字可能是 4，这打破了假设） ，但我对这种复杂性不感兴趣（我假设序列足以找到真实周期）。另外问题是序列可以在期间的中间停止：[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, ...]（期间仍然是 1, 2, 3）。
我还需要找到最小的偏移量和周期。例如对于原始序列，偏移量可以是[0, 1, 4, 0, 0]和周期[1, 1, 2, 3, 7, 0, 0]，但最小的是[0, 1, 4]和[0, 0, 1, 1, 2, 3, 7]。
我的低效方法是尝试每一个可能的偏移量和每一个可能的周期。使用此数据构建序列并检查它是否与原始序列相同。我没有做任何正常的分析，但看起来它至少在时间复杂度上是二次的。
这是我的快速 python 代码（尚未正确测试）：
def getPeriod(arr):
min_offset, min_period, n = len(arr), len(arr), len(arr)
best_offset, best_period = [], []
for offset in xrange(n):
start = arr[:offset]
for period_len in xrange(1, (n - offset) / 2):
period = arr[offset: offset+period_len]
attempt = (start + period * (n / period_len + 1))[:n]
if attempt == arr:
if period_len < min_period:
best_offset, best_period = start[::], period[::]
min_offset, min_period = len(start), period_len
elif period_len == min_period and len(start) < min_offset:
best_offset, best_period = start[::], period[::]
min_offset, min_period = len(start), period_len
return best_offset, best_period
哪个 returns 我想要我的原始序列：
offset [0, 1, 4]
period [0, 0, 1, 1, 2, 3, 7]
还有什么更高效的吗？
我将从构建序列中值的直方图开始
所以你只需列出所有按顺序使用的数字（或其中的重要部分）并计算它们的出现次数。这是
O(n)，其中n是序列大小。对直方图进行升序排序
这是
O(m.log(m))，其中m是不同值的数量。您还可以忽略最有可能在偏移中的低概率数字 (count<treshold)，或者只是进一步降低m的不规则性。对于周期性序列m <<< n，因此无论序列是否周期性，您都可以将其用作第一个标记。找出经期
在 直方图 中，
counts应该是n/period的倍数。所以直方图的approximate/findGCD算了。问题是您需要考虑计数和n（偏移部分）中存在的不规则性，因此您需要大约计算 GCD。例如：sequence = { 1,1,2,3,3,1,2,3,3,1,2,3,3 }已排序直方图：
item,count 2 3 1 4 3 6GCD(6,4)=2和GCD(6,3)=3你应该至少检查+/-1GCD结果，这样可能的周期是：T = ~n/2 = 13/2 = 6 T = ~n/3 = 13/3 = 4所以检查
T={3,4,5,6,7}只是为了确定。在最高计数与最低计数之间始终使用 GCD。如果序列有很多不同的数字，你也可以做一个计数直方图，只检查最常见的值。要检查周期有效性，只需取序列末尾或中间的任何项目（只需使用可能的周期区域）。然后在它发生之前（或之后）的可能时期附近的附近区域寻找它。如果找到几次你就得到了正确的时期（或其倍数）
获取准确的周期
只需检查找到的周期分数 (
T/2, T/3,...) 或对找到的周期做一个直方图，最小的count告诉您封装了多少个实际周期，所以除以它.查找偏移量
当您知道经期时，这很容易。只需从头开始扫描第一项，然后查看经期后是否再次出现。如果不记得位置。在序列的末尾或中间停止……或在某些门槛上取得成功。这最多
O(n)最后记住的位置是offset中的最后一项。
[edit1] 很好奇所以我尝试用 C++ 编写代码
我 simplified/skip 一些东西（假设至少有一半的数组是周期性的）来测试我是否在我的算法中没有犯一些愚蠢的错误，这里的结果（按预期工作）：
const int p=10; // min periods for testing
const int n=500; // generated sequence size
int seq[n]; // generated sequence
int offset,period; // generated properties
int i,j,k,e,t0,T;
int hval[n],hcnt[n],hs; // histogram
// generate periodic sequence
Randomize();
offset=Random(n/5);
period=5+Random(n/5);
for (i=0;i<offset+period;i++) seq[i]=Random(n);
for (i=offset,j=i+period;j<n;i++,j++) seq[j]=seq[i];
if ((offset)&&(seq[offset-1]==seq[offset-1+period])) seq[offset-1]++;
// compute histogram O(n) on last half of it
for (hs=0,i=n>>1;i<n;i++)
{
for (e=seq[i],j=0;j<hs;j++)
if (hval[j]==e) { hcnt[j]++; j=-1; break; }
if (j>=0) { hval[hs]=e; hcnt[hs]=1; hs++; }
}
// bubble sort histogram asc O(m^2)
for (e=1,j=hs;e;j--)
for (e=0,i=1;i<j;i++)
if (hcnt[i-1]>hcnt[i])
{ e=hval[i-1]; hval[i-1]=hval[i]; hval[i]=e;
e=hcnt[i-1]; hcnt[i-1]=hcnt[i]; hcnt[i]=e; e=1; }
// test possible periods
for (j=0;j<hs;j++)
if ((!j)||(hcnt[j]!=hcnt[j-1])) // distinct counts only
if (hcnt[j]>1) // more then 1 occurence
for (T=(n>>1)/(hcnt[j]+1);T<=(n>>1)/(hcnt[j]-1);T++)
{
for (i=n-1,e=seq[i],i-=T,k=0;(i>=(n>>1))&&(k<p)&&(e==seq[i]);i-=T,k++);
if ((k>=p)||(i<n>>1)) { j=hs; break; }
}
// compute histogram O(T) on last multiple of period
for (hs=0,i=n-T;i<n;i++)
{
for (e=seq[i],j=0;j<hs;j++)
if (hval[j]==e) { hcnt[j]++; j=-1; break; }
if (j>=0) { hval[hs]=e; hcnt[hs]=1; hs++; }
}
// least count is the period multiple O(m)
for (e=hcnt[0],i=0;i<hs;i++) if (e>hcnt[i]) e=hcnt[i];
if (e) T/=e;
// check/handle error
if (T!=period)
{
return;
}
// search offset size O(n)
for (t0=-1,i=0;i<n-T;i++)
if (seq[i]!=seq[i+T]) t0=i;
t0++;
// check/handle error
if (t0!=offset)
{
return;
}
代码仍未优化。对于 n=10000，我的设置大约需要 5ms。结果在 t0（偏移量）和 T（句点）中。 您可能需要稍微调整一下阈值常量
备注:如果有句点P1长度为 L，那么还有一段P2，长度相同，L，使得输入序列恰好以 P2 结束（ 即 我们没有在末尾涉及部分周期）。
的确，通过改变offset总能得到相同长度的不同周期。新周期将是初始周期的轮换。
例如，以下序列的周期长度为 4，偏移量为 3：
0 0 0 (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2
但它也有一个长度相同且偏移量为 5 的句点，末尾没有部分句点：
0 0 0 1 2 (3 4 1 2) (3 4 1 2) (3 4 1 2) (3 4 1 2) (3 4 1 2)
言下之意，我们可以通过逆序处理序列，从末尾开始使用零偏移量来查找最小周期，从而找到周期的最小长度。一种可能的方法是简单地在反向列表上使用您当前的算法，而不需要对偏移量进行循环。
既然我们知道了所需周期的长度，我们也可以找到它的最小偏移量。一种可能的方法是尝试所有不同的偏移量（优点是不需要循环长度，因为长度是已知的），但是，如果需要，可以进一步优化，例如通过推进尽可能多地从末尾处理列表，允许周期的最终重复（即最接近未反转序列开始的那个）是部分的。
我不得不做一次类似的事情。我使用了蛮力和一些常识，解决方案不是很优雅，但它有效。该解决方案始终有效，但您必须在函数中设置正确的参数 (k,j, con)。
- 序列在变量seq. 中保存为列表
- k 是序列数组的大小，如果你认为你的序列需要很长时间才能变成周期性的，那么将这个 k 设置为一个很大的数字。
- 变量 found 会告诉我们数组是否通过周期测试 j
- j是周期
- 如果您期望一个大周期，那么您必须将 j 设置为一个大数字。
- 我们通过检查序列的最后 j+30 个数字来测试周期性。
- 周期越大(j)越需要检查
- 一旦其中一个测试通过，我们就退出该函数，我们 return 较小的周期。
您可能会注意到准确性取决于变量 j 和 k 但如果您将它们设置为非常大的数字，它总是正确。
def some_sequence(s0, a, b, m):
try:
seq=[s0]
snext=s0
findseq=True
k=0
while findseq:
snext= (a*snext+b)%m
seq.append(snext)
#UNTIL THIS PART IS JUST TO CREATE THE SEQUENCE (seq) SO IS NOT IMPORTANT
k=k+1
if k>20000:
# I IS OUR LIST INDEX
for i in range(1,len(seq)):
for j in range(1,1000):
found =True
for con in range(j+30):
#THE TRICK IS TO START FROM BEHIND
if not (seq[-i-con]==seq[-i-j-con]):
found = False
if found:
minT=j
findseq=False
return minT
except:
return None
简化版
def get_min_period(sequence,max_period,test_numb):
seq=sequence
if max_period+test_numb > len(sequence):
print("max_period+test_numb cannot be bigger than the seq length")
return 1
for i in range(1,len(seq)):
for j in range(1,max_period):
found =True
for con in range(j+test_numb):
if not (seq[-i-con]==seq[-i-j-con]):
found = False
if found:
minT=j
return minT
其中 max_period 是您要查找的最大周期，test_numb 是多少您要测试的序列号，越大越好，但您必须 max_period+test_numb < len(sequence)