Перечисляя все возможные последовательности, когда задано множество N чисел и диапазона для каждого из чисел N

Question

Постановка задачи:

Мы дали

1. Набор Т чисел S1, S2, .... СТ

2. целое число называется диапазон

Это означает, что S1 может взять на себя (2 * Range + 1) V (S1-Range, S1-Range + 1, ... S1, S1 + 1, .... S1 + Range) Аналогично S2, ... ST может принимать 2 * Диапазон + 1 значения

Проблема 1. Как я перечисляю все возможные последовательности? Т.е. все последовательности (2 * Range-1)^T (S1-Range, S2, ... ST), S1-Range + 1, S2, ... ST), ....., (S1, S2 -Range, S3, .... ST) и т. Д.

Задача 2: Как только перечислять последовательности, сумма которых равна S1 + S2 + ... + ST?

Для задачи 1: Подход я рассматриваю сделать

for (i=0; i<pow(Range,T);i++) 
{ 
    Sequences that can be derived from i are 
    1. {Si + i mod pow(Range,i)} 
    2. {Si - i mod pow(Range,i)} 
} 

Любой другой более элегантное решение?

Кроме того, любые идеи для проблемы 2?

Answer 1

Для # 1, один из способов думать об этом, как о том, как вы увеличиваете число. Вы увеличиваете последнюю цифру, и когда она переполняется, вы возвращаете ее на начальное значение (0) и увеличиваете следующую цифру.

Итак, создайте массив размера T, затем инициализируйте элементы (S1-Range, S2-Range, ..., ST-Range). Распечатайте его.

Теперь увеличьте последнее значение до ST-Range + 1. Распечатайте его. Продолжайте увеличивать и печатать до достижения диапазона ST +. При попытке увеличения, вернитесь в ST-Range, затем переместите одну позицию влево и увеличьте ее. Повторяйте, если это переполнение тоже. Если вы двигаетесь полностью, все готово, иначе распечатайте его.

// Input: T, S[T], Range 
create V[T] 
for (i in 1..T): 
    V[i] = S[i] - Range 
loop forever { 
    print V 
    i = T 
    V[i]++ 
    while V[i] > S[i] + Range { 
     V[i] = S[i] - Range 
     i-- 
     if i < 1: 
      return // we're done 
     V[i]++ 
    } 
} 

---

Для # 2, это немного по-другому. Для описания я проигнорирую значения S и фокус дельта (-Range, ..., 0, ..., + Range) для каждой позиции, называя ее D.

С sum (D) = 0, начальный набор значений: (-Range, -Range, ..., + Range, + Range). Если T четное, первая половина равна -Range, а вторая половина + Range. Если T является нечетным, то среднее значение равно 0.

Теперь посмотрим на то, как вы хотите витки пойти:

-2 -2 0 2 2 
-2 -2 1 1 2 
-2 -2 1 2 1 
-2 -2 2 0 2 (A) 
-2 -2 2 1 1 
-2 -2 2 2 0 
-2 -1 -1 2 2 
-2 -1 0 1 2 
-2 -1 0 2 1 
-2 -1 1 0 2 

Логика здесь в том, что вы пропустите последнюю цифру, так как это всегда функция другие цифры. Вы увеличиваете правую цифру, которая может быть увеличена, и сбросьте цифры справа от нее до более низких возможных значений, которые дадут сумму (D) = 0.

Логика немного сложнее, поэтому я позволю вам повеселиться.;-)

Хороший метод помощника считался бы способом сброса цифр после определенного положения до их наименьшего возможного значения, учитывая начальную дельта. Затем вы можете использовать его для инициализации массива с помощью вызова reset(1, 0), т. Е. Сбросить позиции 1..T, используя начальную дельта 0.

Затем, когда вы увеличиваете D [3] до 2 на шаге, отмеченном A выше, вы вызываете reset(4, -2), т.е. сбросите позиции 4..5, используя начальную дельта -2. При максимальном значении 2 (диапазон) для последней цифры значение D [4] не может быть ниже 0.