Перечисление m-кортежей целых чисел с учетом ограничений импликации - PullRequest
Новая
       35

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

1 голос
/ 11 августа 2010

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

  1. Для каждого i в {1, ..., m} существует число n [i]> = 0, такое что a [i] <= n [i]. </p>

  2. Для каждой упорядоченной пары (i, j) с i, j в {1, ..., m} существуют числа c [i] [j], d [i] [j]> = 0 такое, что:

    если a [i]> c [i] [j], то a [j] <= d [i] [j]. </p>

  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. Теперь давайте рассмотрим алгоритм.

Начните с a [1] = 0: n [2] не изменяется, потому что a [1] <= 0. Мы печатаем (0,0), (0,1), (0,2). </p>

Далее следует [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].

1 Ответ

0 голосов
/ 21 августа 2010

интересная проблема.

Обратите внимание, что время обязательно пропорционально числу кортежей, которые должны быть перечислены.Таким образом, невозможно асимптотически улучшить то, что у вас есть.

С точки зрения длины кода, это не может быть оптимальным, если не считать длинного кадра.Вам просто не нужно кодировать отдельный цикл for для каждого i = 1..m

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

...