Перечисляя в бесконечность в более чем двух измерениях

Question

Если я хочу, чтобы перечислить через все комбинации несколько ограниченных значений, это достаточно легко:

for(int i = 0; i <= iMax; i++) 
{ 
    for(int j = 0; j <= jMax; j++) 
    { 
     for(int k = 0; k <= kMax; k++) 
     { 
      DoSomething(i,j); 
     } 
    } 
} 

Точно так же, если я хочу, чтобы перечислить над одного неограниченной значение, проверка некоторого условия, что достаточно легко тоже:

BigInteger i = 0; 
while(true) 
{ 
    if(Condition(i)) { break; } 
    i++; 
} 

Но что перечисляя на все комбинации множественных неограниченная значения? За два, один из способов я знаю это "зиг-заг", например, так:

BigInteger i = 0; 
BigInteger j = 0; 
bool direction = true; 
while(true) 
{ 
    if(Condition(i,j)) { break; } 

    if(direction) 
    { 
     if(j==0) 
     { 
      direction = false; 
      i++; 
     } 
     else 
     { 
      i++; 
      j--; 
     } 
    } 
    else 
    { 
     if(i==0) 
     { 
      direction = true; 
      j++; 
     } 
     else 
     { 
      j++; 
      i--; 
     } 
    } 
} 

Первые несколько (i, j) пар это будет производить являются: (0,0), (1 , 0), (0,1), (0,2), (1,1), (2,0), (3,0), (2,1), (1,2) ...

Итак, мой вопрос: как этот или какой-либо другой метод можно адаптировать для более чем двух измерений? например Если я хочу перебрать i, j и k?

Примечание: Я знаю, что есть лучшие способы написания этих примеров, я просто написал их как можно проще для простоты.

Answer 1

for(limit=0;;++limit) { 
    for(i0=0; i0<=limit; ++i0) { 
    for(i1=0; i1<=limit-i0; ++i1) { 
     for(i2=0; i2<=limit-i0-i1, ++i2) { 
     for(i3=0; i3<=limit-i0-i1-i2, ++i3) { 
      int i4 = limit-i0-i1-i2-i3; 
      //do stuff with i0, i1, i2, i3, i4; break when had enough 
     }}}}}} 

Answer 2

Это действительно проблема комбинаторики, а не проблема компьютерного программирования.

В любом случае, вы можете подойти к этому неограничена MultiVariable проблему таким образом:

At level 0, you have 1 problem to check [0,0,0] At level 1, you have 3 problems to check ([0,0,1],[0,1,0],[1,0,0]) At level 2, you have 6 problems ([0,0,2],[0,2,0],[2,0,0],[0,1,1],[1,0,1],[1,1,0])

так что вы должны создать все Каковы возможности (рекурсия может помочь) для каждого уровня

Answer 3

Итак, одно измерение легко, как вы упомянули. Просто подсчитайте с нуля.

Два тоже не так уж трудно, просто посчитать по диагонали:

 
11 
7 12 
4 8 13 
2 5 9 14 
1 3 6 10 15

Для трех измерений мы можем представить себе пирамиду, в которой мы добавляем новую оболочку каждый раз:

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

 
1

---

 
1 
2 1

---

 
1 
2 1 
3 2 1

Вы можете представить себе эту 3 размерную диаграмму, как добавление оболочек вокруг сферы (но переехали в дискретный, а не непрерывный, масштабе), 2-мерная версии, как концентрические круги и 1-мерная версия как радиус этих концентрических окружностей. Конечно, во всех случаях у нас всего лишь 1/4 картины, так как вы ограничиваете все положительными значениями.

Итак, как это сделать в n-м случае.

Ну, каждая оболочка представляется каждой комбинацией значений для каждого измерения так, что их сумма является некоторой константой. Итак, сначала вы найдете каждую комбинацию натуральных чисел для каждого измерения, так что их сумма равна 1, тогда вы найдете все комбинации, которые суммируются до 2, тогда вы найдете все комбинации, суммирующие до 3, и вы продолжаете до бесконечности.

Answer 4

В 2D: сгенерировать все пары (j, k) такие, что j + k == i, для увеличения i.

for (i= 0; true; i++) 
    for (j= 0, k= i; 0 <= k; j++, k--) 


i=0 -> (0, 0) 
i=1 -> (0, 1), (1, 0) 
i=2 -> (0, 2), (1, 1), (2, 0) 
... 

В 3D: генерировать все троек (J, L, M) такой, что L + M == J для увеличения J и J + K = I, I для увеличения.

for (i= 0; true; i++) 
    for (j= 0, k= i; 0 <= k; j++, k--) 
    for (l= 0, m= j; 0 <= m; l++, m--) 


i=0, j=0 -> (0, 0, 0) 
i=1, j=0 -> (0, 0, 1), (0, 1, 0) 
i=1, j=1 -> (1, 0, 1), (1, 1, 0) 
i=2, j=0 -> (0, 0, 2), (0, 1, 1), (0, 2, 0) 
i=2, j=1 -> (1, 0, 2), (1, 1, 1), (1, 2, 0) 
i=2, j=2 -> (2, 0, 2), (2, 1, 1), (2, 2, 0) 
...