测试列表修改是否为periodi

Question

我有一个list的整数，它在一个循环中不断被修改，我需要知道它的内容是否在经过一定的迭代后重复以打破循环。你知道吗

如果没有，则list最终将修改为[]，或者循环在达到某个迭代限制时终止。到目前为止，我的解决方案是：

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

首先请允许我说，所有的列表都是周期性的，如果你考虑一个足够大的周期的话。你知道吗

也就是说，这可能是使用布卢姆过滤器的好地方，例如： https://pypi.python.org/pypi/drs-bloom-filter/

bloomfilters是一种集合，它可以非常快速地执行集合成员身份测试，并且可以在不实际存储元素数据的情况下向集合添加内容。这意味着它是概率的，但是你可以调整概率。在检测到bloom时，您可以使用一个快速检查算法来确认匹配，因此您可以使用一个确定的bloom+来检测结果。你知道吗

用法如下：

In [1]: import bloom_filter_mod

In [2]: bloom_filter = bloom_filter_mod.Bloom_filter(1000000, 0.01)

In [3]: for i in range(10):
   ...:     bloom_filter.add(i)
   ...:

In [4]: for i in range(0, 20, 2):
   ...:     if i in bloom_filter:
   ...:         print('{} present'.format(i))
   ...:
0 present
2 present
4 present
6 present
8 present

1000000是要存储在筛选器中的最大元素数，0.01是满时出现误报的最大概率。你知道吗

因此，您可以“存储”过滤器中的每个子序列，并快速检测复发。你知道吗

Answer 2

好的，有发现。 如果您查看列表中的最后一个元素，我们将其命名为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 toclient函数。你知道吗

因此，这大大减少了必须存储在历史记录中的列表配置的数量。只需每隔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]);

Answer 3

你的list（顺便说一下，你真的应该重命名它）在baseb中存储一个modb**something数字。每次运行modify都将数字乘以a，然后在表示的末尾截断零。你知道吗

调用最初由列表n表示的号码，并调用列表的原始长度l。如果这个过程终止，它将在第一次迭代k时这样做，使得b**l除以n * a**k，只有当且仅当b**l / gcd(n, b**l)的所有素数因子都是a的因子时才会发生。这很容易确定：

def all_prime_factors_of_first_divide_second(a, b):
    while a != 1:
        factor = gcd(a, b)
        if factor == 1:
            return False
        while not a % factor:
            a //= factor
    return True