함축적 인 내용의 m- 튜플을 열거 함

Question

다음 제한 조건에 부합하는 음수가 아닌 모든 m- 튜플 (a [1], ..., a [m])을 열거하려면 어떻게합니까? 각각에

1. 는

   의 {1, ..., m}, 수 인 N I [I]> = 0 예 [I] < = N [즉.

2. {1, ..., m}의 i, j를 갖는 각각의 순서쌍 (i, j)에 대해 번호 c [i] [j], d [i] [j] [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이라고합시다. 이제 알고리즘을 살펴 보겠습니다.

[1] = 0 : n [2]는 [1] < = 0이므로 변경되지 않습니다. (0,0), (0,1), (0,2)를 출력합니다.

다음은 a [1]> c [1] [2], n [2]가 루프에서 min {n [2], d [1] [j ]} = 0. 우리는 (1,0)을 인쇄합니다. [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이 될 것입니다 (제약 조건이 하나 인 사소한 경우 제외).