python - 测试列表修改是否是周期性的

Question

我有一个整数列表，它在循环中不断修改，我需要判断它的内容在一定数量的迭代后是否会重复以打破循环。

如果没有，列表最终将修改为[]，或者当达到一定的迭代限制时循环终止。到目前为止我的解决方案:

def modify(numlist, a, b):
    numlist = [(x * a) for x in numlist]
    for i in range((len(numlist) - 1), 0, -1):
        if numlist[i] >= b: numlist[i - 1] += numlist[i] // b
        numlist[i] = numlist[i] % b
    numlist[0] %= b
    while numlist[-1] == 0:
        numlist.pop(-1)
        if numlist == []: break 

numlist = [1, 2, 3, 4, 5]
listHistory = [numlist]
a, b = someValue, anotherValue

n = 0
while numlist != [] and n <= limit:
    modify(numlist, int(a), int(b))
    listHistory.append(numlist)
    if numlist in listHistory: break
    n += 1

limit 可以非常大(大约 10**6 - 10**7)并检查当前的 numlist 相对于所有以前的版本来说变得非常慢。

有没有更有效的方法来做到这一点，甚至有一种方法可以通过列表初始内容和给定的a、b来预先确定修改是否是周期性的？

Answer 1

好的，有东西了。如果您查看列表中的最后一个元素，我们将其称为 m。发生了什么，它会乘以 a，然后对 b 取模。它永远不会与任何其他元素混合，因此如果列表的配置必须重复自身，则必须保留以下内容:

m*a^n=m modulo b
<==>a^n=1 modulo b
<  >a^(n+1)=a modulo b

这是一个你可以利用 Fermats little theorem 的问题如果 a 和 b 互质，则

a^phi(b)=1 modulo b

其中phi是Eulers totient函数。

因此，这会大大减少您必须存储在历史记录中的列表配置的数量。您只需在每个 phi(b) 步骤中存储它即可。

我在这里找到了 phi 的实现: Computing Eulers Totient Function

更新:

好的，如果您要执行 += list[i] % b 而不是 += list[i]//b，我找到了一个快速解决方案。否则，在最坏的情况下您需要 b^4*phi(b) 步骤

更新2:

我用C重写了代码(见下文)以使其更快，并实现了@user2357112提出的“龟兔赛跑”算法。这样我可以每秒检查几百万个循环，这应该比 python 实现快得多。我尝试了一些不同的值组合:

a  b    steps     b^4*phi(b)  (b/GCD(b,a))^4*phi(b/GCD(n,a))    (b/GCD(b,a))^4*phi(b/GCD(n,a))/steps
2  37   67469796  67469796    67469796                          1
3  37   33734898  67469796    67469796                          2
4  37   33734898  67469796    67469796                          2
5  37   67469796  67469796    67469796                          1
6  37   7496644   67469796    67469796                          9
7  37   16867449  67469796    67469796                          4
36 37   3748322   67469796    67469796                          18
2  36   39366     20155392    629856                            16
3  36   256       20155392    82944                             27648
4  36   19683     20155392    39366                             2
5  36   5038848   20155392    20155392                          4

所以你知道这是怎么回事了:循环长度似乎总是(b/GCD(b,a))^4*phi(b/GCD(n,a))的除数，所以最坏的情况是怀疑的 (b/GCD(b,a))^4*phi(b/GCD(n,a)) 步骤

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void modify(int *, int, int);
void printl(int * );
int main(int argc, const char*argv[])
{
  int l[5]={1,2,3,4,5};
  int lz[5]={1,2,3,4,5};
  int i=1,a,b,n;
  if (argc<4) {
    printf("Not enough arguments!!\n");
    exit(1);
  }
  a=atoi(argv[1]);
  b=atoi(argv[2]);
  n=atoi(argv[3]);
  modify(l,a,b);
  while (i<n) {
    modify(l,a,b);
    modify(l,a,b);
    modify(lz,a,b);
    i++;
    if (memcmp(l,lz,sizeof(l))==0) {
      printf("success!\n");
      break;
    }
    if (i%1000000==0) printf("Step %d.000.000\n",i/1000000);
  }
  printf("Final step:  %d\n",i);
  printl(l);
  printl(lz);
  return 0;

}
void  modify(int * li, int a, int b) {
  int i=0;
  while (i<=4) {
   li[i]*=a;
   i++;
  }
  i=4;
  while (i>=1) {
    if (li[i]>=b) {
      li[i-1]+=li[i]/b;
    }
    li[i]=li[i]%b;
    i--;

  }
  li[0]=li[0]%b;
}
void printl(int * li) {
  printf("l=(%d,%d,%d,%d,%d)\n",li[0],li[1],li[2],li[3],li[4]);