Python中使用序列解决不确定循环层数的遍历问题

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

如果遇到循环层数是变量的情况如何解决？

问题引入，有属性集：

属性	属性类别	数据标号
r1	0	1,2,3,4
r1	1	5,6,7,8,9,10
r2	0	1,8,9,10
r2	1	2,3,7
r2	2	4,5,6
r3	0	1,3,5,7,9
r3	1	2,4,6,8,10

根据属性的类别可以求出初等集：

r1,r2,r3	数据标号
0,0,0	1
0,0,1	None
0,1,0	3
0,1,1	2
0,2,0	None
0,2,1	4
1,0,0	9
1,0,1	8,10
1,1,0	7
1,1,1	None
1,2,0	5
1,2,1	6

一个最直观的解法是：

data = [
    [set([1,2,3,4]), set([5,6,7,8,9,10])],
    [set([1,8,9,10]), set([2,3,7]), set([4,5,6])],
    [set([1,3,5,7,9]), set([2,4,6,8,10])]
]

# len(r1)是r1的类别数，2
# 后面类似
for i in range(len(r1)):
    for j in range(len(r2)):
        for k in range(len(r3)):
            # 求三个属性集合的交集
            print(data[0][i] & data[1][j] & data[2][k])

对于上面的确定问题来说，这个方法已经足够，但是考虑到更为一般的情况，属性个数是不确定的，可能有很多个，这就意味着for将会有很多层，这个不确定循环层数的问题导致上面的思路将无法解决问题。

因此，我们需要换一个思路，由于不能动态决定循环层数，我们就不采用for循环的做法，思路简单描述为：

首先我们生成一个长度为属性长度的索引：

# index为[0]*属性个数，在上面的例子中为[0,0,0]
index = [0] * len(data)
# index_max为index的最大值，在上面的例子中为[2,3,2]
index_max = [len(d) for d in data]

然后读取index的初等集为：

def get(data, index):
    out = data[0][index[0]]
    for i in range(1, len(index)):
        out = out & data[i][index[i]]
    return out

更新index，可以获取新的index：

def add(index, index_max):
    for i in range(1, len(index) + 1):
        index[-i] += 1
        if index[-i] < index_max[-i]:
            break
        index[-i] %= index_max[-i]

把上面的思路结合起来就是：

data = [
    [set([1,2,3,4]), set([5,6,7,8,9,10])],
    [set([1,8,9,10]), set([2,3,7]), set([4,5,6])],
    [set([1,3,5,7,9]), set([2,4,6,8,10])]
]

index = [0] * len(data)
index_max = [len(d) for d in data]
steps = sum(index_max)

def get(data, index):
    out = data[0][index[0]]
    for i in range(1, len(index)):
        out = out & data[i][index[i]]
    return out


def add(index, index_max):
    for i in range(1, len(index) + 1):
        index[-i] += 1
        if index[-i] < index_max[-i]:
            break
        index[-i] %= index_max[-i]

out = []
for i in range(0, steps):
    out.append(get(data, index))
    add(index, index_max)

将这个算法思路做个比喻的话，就是index就是时间值，index_max是时间的最大值，steps是从开始到最大值所需要的次数，每次add就是增加时间值，每次get就是获取在index时间值时的一个初等集，当我们add够steps次，那么就完成了对初等集的完整获取，out就是最后的结果。

这样我们通过可变长度的序列化解了不确定循环层数的问题，所有类似需要不确定循环次数的问题可以借鉴该思路转化求解。