如何计算数组可变步长循环排列的迭代次数？

需求概述 #

我需要实现一个功能：打印并计数数组的循环排列子集，函数输入为数组、步长和起始值。数组元素不限于数字，比如含5个元素的数组X, 1, 2, 3, Y，步长为3时，生成的不重复循环排列子集如下：

X, 1, 2     // 第一行
3, Y, X
1, 2, 3
Y, X, 1
2, 3, Y     // 此后开始重复，停止迭代

此时迭代次数为5；8元素数组步长为4时迭代次数为2，步长为6时为4。

数组允许包含重复元素，比如LI, LI, 1, 2, 3, LO, LO这类数组，步长为2时生成的子集序列为LI LI | 1 2 | 3 LO | LO LI | LI 1 | 2 3 | LO LO，迭代次数为7。要求生成的子集是连续的步长长度序列，无空值，所有元素保持原数值且被使用。

我用Python实现，获取循环数组数据没问题，但需要确定迭代的移位次数。目前已有一个Python函数可以计算该次数，但希望找到对应的数学公式：

def getiterations(elements, stride):
    # 假设 elements > stride
    lc = 0
    lineno = 0
    finished = False
    while not finished:
        lc = lc + stride      # 模拟取N个元素
        lineno = lineno + 1
        if (lc % elements) == 0:
           finished = True
    return lineno

对应的数学公式 #

迭代次数的数学计算公式为：
迭代次数 = 数组长度 / gcd(数组长度, 步长)
其中gcd(a,b)表示a和b的最大公约数。

公式原理 #

我们需要找到最小的迭代次数n，使得累计取的总元素数n*步长是数组长度的整数倍（因为循环数组中，总元素数达到数组长度的整数倍时，就会回到起始位置，后续生成的子集开始重复）。

换句话说，要找最小的正整数n，满足n*stride ≡ 0 mod elements，也就是n*stride是elements的倍数。根据数论知识，最小的n等于elements除以elements和stride的最大公约数，因为此时n*stride恰好是两者的最小公倍数，对应第一次回到起点的时刻。

用公式改写Python函数 #

可以利用Python标准库math.gcd实现更高效的计算（注意math.gcd仅处理非负整数，需确保输入的数组长度和步长为正整数）：

import math

def getiterations(elements, stride):
    return elements // math.gcd(elements, stride)

验证例子 #

• 5元素数组，步长3：gcd(5,3)=1，5//1=5，符合迭代次数5
• 8元素数组，步长4：gcd(8,4)=4，8//4=2，符合迭代次数2
• 8元素数组，步长6：gcd(8,6)=2，8//2=4，符合迭代次数4
• 7元素数组（LI, LI, 1, 2, 3, LO, LO），步长2：gcd(7,2)=1，7//1=7，符合迭代次数7

内容的提问来源于stack exchange，提问作者MyICQ