枚举受蕴涵约束的整数 m 元组

Question

如何枚举所有 m 元组非负整数 (a[1],...,a[m]) 并遵守以下约束？

1. 对于 {1,...,m} 中的每个 i，都有一个数字 n[i] >= 0，使得 a[i] <= n[i]。

2. 对于 {1,...,m} 中 i,j 的每个有序对 (i,j)，有数字 c[i][j], d[i][j] >= 0 这样那：

   如果a[i]> c[i][j]，则 a[j] <= d[i][j]。

3. c[i][j] = c[j][i]。

到目前为止，我已经提出了以下解决方案。有没有更有效的方法来做到这一点？我正在使用 C 或 C++ 进行编程。

for a[1]=0,...,n[1] do 
{
    for j=2,...,m do
    {
        if a[1] > c[1][j] then n[j]:=min{n[j],d[1][j]}
                          else n[j]:=n[j]
    }
    for a[2]=0,...,n[2] do 
    {
        for j=3,...,m do
        {
            if a[2] > c[2][j] then n[j]:=min{n[j],d[2][j]}
                              else n[j]:=n[j]
        }
        for a[3]=0,...,n[3] do
        {
            .
            .
            .
            for a[m]=0,...,n[m] do
            {
                print (a[1],...,a[m])
            }
        }...}}

我发现该算法存在一个主要的低效率问题。为了简单起见，取 m=2。假设对于所有 i,j，n[1] = n[2] = 2 且 c[i][j] = d[i][j] = 0。现在让我们看一下算法。

从 a[1] = 0 开始：n[2] 不变，因为 a[1] <= 0。我们打印 (0,0),(0,1),(0,2)。

接下来是a[1] = 1：因为a[1] > c[1][2], n[2] 在循环中更改为 min{ n[2],d[1][j] } = 0。我们打印 (1,0)。

最后a[1] = 2：因为a[1]> c[1][2], n[2] 在循环中改为 min{ n[2],d[1][j] } = 0。（我们只是做了和以前一样的事情。这就是低效率。 ) 我们打印(2,0)。

备注：对于我的应用，可以假设 c[i][j]=d[i][j]。

Answer 1

一个有趣的问题。

请注意，时间必然与要枚举的元组的数量成正比。所以不可能渐进地改进你所拥有的东西。

就代码长度而言，这不可能是最佳的，至少不是最佳的。你根本不必为每个 i = 1..m 编写一个单独的 for 循环，

稍后我可能会对算法进行修改；但长话短说，运行时间将以 m 为指数（除了约束等于 1 的小情况）。