Перечисление m-кортежей целых чисел с ограничениями на импликацию

Question

Как перечислить все m-кортежи неотрицательных целых чисел (a [1], ..., a [m]) с учетом следующих ограничений?

1. Для каждого я в {1, ..., т}, существует такое число п [I]> = 0 так, что [я] < = п [I].

2. Для каждой упорядоченной пары (i, j) с i, j в {1, ..., m} существуют числа 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 для простоты. Скажем n [1] = n [2] = 2 и c [i] [j] = d [i] [j] = 0 для всех i, j. Теперь давайте рассмотрим алгоритм.

Начало работы при [1] = 0: n [2] не изменяется, поскольку a [1] < = 0. Мы печатаем (0,0), (0,1), (0,2).

Далее [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

Я могу взять удар по алгоритму позже; но, чтобы сделать длинную историю коротким, время работы будет экспоненциальным в m (за исключением тривиальных случаев, когда ограничения равны единице.)