Нерекурсивное перечисление трехзначно положительных целочисленных композиций

Question

После создания итеративной (нерекурсивной) функции, которая перечисляет дважды ограниченные композиции натуральных чисел в лексикографическом порядке для микроконтроллера с очень небольшим объемом ОЗУ ( но большой EPROM) мне пришлось расширить количество ограничений до 3, а именно:

1. Ограничение на длину композиции
2. Ограничение на минимальное значение элементов
3. Ограничение на максимальное значение элементов

Оригинальная функция, которая генерирует дважды ограниченные композиции, приведена ниже:

void GenCompositions(unsigned int myInt, unsigned int CompositionLen, unsigned int MinVal)
{
    if ((MinVal = MinPartitionVal(myInt, CompositionLen, MinVal, (unsigned int) (-1))) == (unsigned int)(-1)) // Increase the MinVal to the minimum that is feasible.
        return;

    std::vector<unsigned int> v(CompositionLen);
    int pos = 0;
    const int last = CompositionLen - 1;


    for (unsigned int i = 1; i <= last; ++i) // Generate the initial composition
        v[i] = MinVal;

    unsigned int MaxVal = myInt - MinVal * last;
    v[0] = MaxVal;

    do
    {
        DispVector(v);

        if (pos == last)
        {
            if (v[last] == MaxVal)
                break;

            for (--pos; v[pos] == MinVal; --pos);  //Search for the position of the Least Significant non-MinVal (not including the Least Significant position / the last position).
            //std::cout << std::setw(pos * 3 + 1) << "" << "v" << std::endl;    //DEBUG

            --v[pos++];
            if (pos != last)
            {
                v[pos] = v[last] + 1;
                v[last] = MinVal;
            }
            else
                v[pos] += 1;

        }
        else
        {
            --v[pos];
            v[++pos] = MinVal + 1;
        }

    } while (true);
}

Пример выходных данных этой функции:

GenCompositions(10,4,1);:
7, 1, 1, 1
6, 2, 1, 1
6, 1, 2, 1
6, 1, 1, 2
5, 3, 1, 1
5, 2, 2, 1
5, 2, 1, 2
5, 1, 3, 1
5, 1, 2, 2
5, 1, 1, 3
4, 4, 1, 1
4, 3, 2, 1
4, 3, 1, 2
4, 2, 3, 1
4, 2, 2, 2
4, 2, 1, 3
4, 1, 4, 1
4, 1, 3, 2
4, 1, 2, 3
4, 1, 1, 4
3, 5, 1, 1
3, 4, 2, 1
3, 4, 1, 2
3, 3, 3, 1
3, 3, 2, 2
3, 3, 1, 3
3, 2, 4, 1
3, 2, 3, 2
3, 2, 2, 3
3, 2, 1, 4
3, 1, 5, 1
3, 1, 4, 2
3, 1, 3, 3
3, 1, 2, 4
3, 1, 1, 5
2, 6, 1, 1
2, 5, 2, 1
2, 5, 1, 2
2, 4, 3, 1
2, 4, 2, 2
2, 4, 1, 3
2, 3, 4, 1
2, 3, 3, 2
2, 3, 2, 3
2, 3, 1, 4
2, 2, 5, 1
2, 2, 4, 2
2, 2, 3, 3
2, 2, 2, 4
2, 2, 1, 5
2, 1, 6, 1
2, 1, 5, 2
2, 1, 4, 3
2, 1, 3, 4
2, 1, 2, 5
2, 1, 1, 6
1, 7, 1, 1
1, 6, 2, 1
1, 6, 1, 2
1, 5, 3, 1
1, 5, 2, 2
1, 5, 1, 3
1, 4, 4, 1
1, 4, 3, 2
1, 4, 2, 3
1, 4, 1, 4
1, 3, 5, 1
1, 3, 4, 2
1, 3, 3, 3
1, 3, 2, 4
1, 3, 1, 5
1, 2, 6, 1
1, 2, 5, 2
1, 2, 4, 3
1, 2, 3, 4
1, 2, 2, 5
1, 2, 1, 6
1, 1, 7, 1
1, 1, 6, 2
1, 1, 5, 3
1, 1, 4, 4
1, 1, 3, 5
1, 1, 2, 6
1, 1, 1, 7

После добавления 3-го ограничения (по максимальному значению элементов) сложность функции значительно возросла. Эта расширенная функция указана ниже:

void GenCompositions(unsigned int myInt, unsigned int CompositionLen, unsigned int MinVal, unsigned int MaxVal)
{
    if ((MaxVal = MaxPartitionVal(myInt, CompositionLen, MinVal, MaxVal)) == 0) //Decrease the MaxVal to the maximum that is feasible.
        return;

    if ((MinVal = MinPartitionVal(myInt, CompositionLen, MinVal, MaxVal)) == (unsigned int)(-1))    //Increase the MinVal to the minimum that is feasible.
        return;

    std::vector<unsigned int> v(CompositionLen);
    unsigned int last = CompositionLen - 1;
    unsigned int rem = myInt - MaxVal - MinVal*(last-1);
    unsigned int pos = 0;

    v[0] = MaxVal;  //Generate the most significant element in the initial composition

    while (rem > MinVal){   //Generate the rest of the initial composition (the highest in the lexicographic order). Spill the remainder left-to-right saturating at MaxVal

        v[++pos] = ( rem > MaxVal ) ? MaxVal : rem;  //Saturate at MaxVal
        rem -= v[pos] - MinVal; //Deduct the used up units (less the background MinValues)
    }

    for (unsigned int i = pos+1; i <= last; i++)    //Fill with MinVal where the spillage of the remainder did not reach.
        v[i] = MinVal;


    if (MinVal == MaxVal){  //Special case - all elements are the same. Only the initial composition is possible.
        DispVector(v);
        return;
    }

    do
    {
        DispVector(v);

        if (pos == last)        
        {       
            for (--pos; v[pos] == MinVal; pos--) {  //Search backwards for the position of the Least Significant non-MinVal (not including the Least Significant position / the last position).
                if (!pos)   
                    return;
            }

            //std::cout << std::setw(pos*3 +1) << "" << "v" << std::endl;  //Debug

            if (v[last] >= MaxVal)  // (v[last] > MaxVal) should never occur
            {

                if (pos == last-1)  //penultimate position. //Skip the iterations that generate excessively large compositions (with elements > MaxVal).
                {   
                    for (rem = MaxVal; ((v[pos] == MinVal) || (v[pos + 1] == MaxVal)); pos--) { //Search backwards for the position of the Least Significant non-extremum (starting from the penultimate position - where the previous "for loop" has finished).  THINK:  Is the (v[pos] == MinVal) condition really necessary here ?
                        rem += v[pos];  //Accumulate the sum of the traversed elements
                        if (!pos)
                            return;
                    }
                    //std::cout << std::setw(pos * 3 + 1) << "" << "v" << std::endl;    //Debug

                    --v[pos];
                    rem -= MinVal*(last - pos - 1) - 1;  //Subtract the MinValues, that are assumed to always be there as a background

                    while (rem > MinVal)    // Spill the remainder left-to-right saturating at MaxVal
                    {
                        v[++pos] = (rem > MaxVal) ? MaxVal : rem;   //Saturate at MaxVal
                        rem -= v[pos] - MinVal; //Deduct the used up units (less the background MinValues)
                    }

                    for (unsigned int i = pos + 1; i <= last; i++)  //Fill with MinVal where the spillage of the remainder did not reach.
                        v[i] = MinVal;

                    continue;   //The skipping of excessively large compositions is complete. Nothing else to adjust...
                }

                /* (pos != last-1) */
                --v[pos];
                v[++pos] = MaxVal;
                v[++pos] = MinVal + 1;  //Propagate the change one step further. THINK: Why a CONSTANT value like MinVal+1 works here at all?

                if (pos != last)
                    v[last] = MinVal;

            }
            else    // (v[last] < MaxVal)
            {           
                --v[pos++];
                if (pos != last)
                {
                    v[pos] = v[last] + 1;
                    v[last] = MinVal;
                }
                else
                    v[pos] += 1;
            }
        }
        else    // (pos != last)
        {
            --v[pos];
            v[++pos] = MinVal + 1;  // THINK: Why a CONSTANT value like MinVal+1 works here at all ?
        }

    } while (true);
}

Пример вывода этой расширенной функции:

GenCompositions(10,4,1,4);:
4, 4, 1, 1
4, 3, 2, 1
4, 3, 1, 2
4, 2, 3, 1
4, 2, 2, 2
4, 2, 1, 3
4, 1, 4, 1
4, 1, 3, 2
4, 1, 2, 3
4, 1, 1, 4
3, 4, 2, 1
3, 4, 1, 2
3, 3, 3, 1
3, 3, 2, 2
3, 3, 1, 3
3, 2, 4, 1
3, 2, 3, 2
3, 2, 2, 3
3, 2, 1, 4
3, 1, 4, 2
3, 1, 3, 3
3, 1, 2, 4
2, 4, 3, 1
2, 4, 2, 2
2, 4, 1, 3
2, 3, 4, 1
2, 3, 3, 2
2, 3, 2, 3
2, 3, 1, 4
2, 2, 4, 2
2, 2, 3, 3
2, 2, 2, 4
2, 1, 4, 3
2, 1, 3, 4
1, 4, 4, 1
1, 4, 3, 2
1, 4, 2, 3
1, 4, 1, 4
1, 3, 4, 2
1, 3, 3, 3
1, 3, 2, 4
1, 2, 4, 3
1, 2, 3, 4
1, 1, 4, 4

ВОПРОС : Где моя реализация ограничения максимального значения элементов пошла не так, чтобы вызвать такое увеличение размера и сложности кода?
IOW: Где находится недостаток в алгоритме, который вызывает появление этого кода после добавления одного простого ограничения <= MaxVal? Можно ли это упростить без рекурсии?

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

#include <iostream>
#include <iomanip>
#include <vector> 

void DispVector(const std::vector<unsigned int>& partition)
{
    for (unsigned int i = 0; i < partition.size() - 1; i++)       //DISPLAY THE VECTOR HERE ...or do sth else with it.
        std::cout << std::setw(2) << partition[i] << ",";

    std::cout << std::setw(2) << partition[partition.size() - 1] << std::endl;
}

unsigned int MaxPartitionVal(const unsigned int myInt, const unsigned int PartitionLen, unsigned int MinVal, unsigned int MaxVal)
{
    if ((myInt < 2) || (PartitionLen < 2) || (PartitionLen > myInt) || (MaxVal < 1) || (MinVal > MaxVal) || (PartitionLen > myInt) || ((PartitionLen*MaxVal) < myInt ) || ((PartitionLen*MinVal) > myInt))  //Sanity checks
        return 0;

    unsigned int last = PartitionLen - 1;

    if (MaxVal + last*MinVal > myInt)
        MaxVal = myInt - last*MinVal;   //It is not always possible to start with the Maximum Value. Decrease it to sth possible

    return MaxVal;
}

unsigned int MinPartitionVal(const unsigned int myInt, const unsigned int PartitionLen, unsigned int MinVal, unsigned int MaxVal)
{
    if ((MaxVal = MaxPartitionVal(myInt, PartitionLen, MinVal, MaxVal)) == 0)   //Assume that MaxVal has precedence over MinVal
        return (unsigned int)(-1);

    unsigned int last = PartitionLen - 1;

    if (MaxVal + last*MinVal > myInt)
        MinVal = myInt - MaxVal - last*MinVal;  //It is not always possible to start with the Minimum Value. Increase it to sth possible

    return MinVal;
}

//
// Put the definition of GenCompositions() here....
//

int main(int argc, char *argv[])
{
    GenCompositions(10, 4, 1, 4);

    return 0;
}

ПРИМЕЧАНИЕ: лексикографический порядок (сверху вниз) композиций, генерируемых этими функциями, не является обязательным. ... и при этом не пропускаются итерации "do loop", которые НЕ генерируют правильные композиции.

Answer 1

Алгоритм

Итеративный алгоритм для создания композиций с ограниченным числом деталей и минимальным и максимальным значением не так уж сложен.Сочетание фиксированной длины и минимального значения на самом деле делает вещи проще;мы можем всегда сохранять минимальное значение в каждой части и просто перемещать «дополнительное» значение для создания различных композиций.

Я буду использовать этот пример:

n=15, length=4, min=3, max=5

Мы начнем с создания композиции с минимальными значениями:

3,3,3,3

, а затем распределим левыйпревышение значения 15 - 12 = 3 над частями, начиная с первой части и двигаясь вправо каждый раз, когда мы достигаем максимального значения:

5,4,3,3

Это первая композиция.Затем мы несколько раз преобразуем композицию, чтобы получить следующую лексикографически обратную, используя следующие правила:

Мы начинаем каждый шаг с нахождения самой правой части, значение которой больше минимального значения. (На самом деле это можно упростить; см. Обновленный пример кода в конце этого ответа.) Если эта часть не последняя, ​​мы вычитаем из нее 1 и добавляем 1 к части справа отэто, например:

5,4,3,3
  ^
5,3,4,3

и это следующая композиция.Если самая правая неминимальная часть является последней частью, все немного сложнее.Мы уменьшаем значение последней части до минимума и сохраняем «дополнительное» значение во временной сумме, например:

3,4,3,5
      ^
3,4,3,3   + 2

Затем мы двигаемся дальше влево, пока не найдем следующую часть, значение которой большечем минимальное значение:

3,4,3,3   + 2
  ^

Если количество частей справа от этой части (2) может содержать временную сумму плюс 1, мы вычитаем 1 из текущей части и добавляем 1 к временнойитого, а затем распределите временное итоговое значение, начиная с части справа от текущей части:

3,3,3,3   + 3
    ^
3,3,5,4

и это наша следующая композиция.Если бы части справа от неминимальной части не могли содержать временную сумму плюс 1, мы бы снова сократили эту часть до минимального значения и добавили «дополнительное» значение к временной сумме, и посмотрели бы дальшеслева, например (используя другой пример с n = 17):

5,3,4,5
      ^
5,3,4,3   + 2
    ^
5,3,3,3   + 3
^
4,3,3,3   + 4
  ^
4,5,5,3

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

3,3,4,5
      ^
3,3,4,3   + 2
    ^
3,3,3,3   + 3
?

Это означает, что 3,3,4,5 был последнимсостав.

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

---

Пример кода

Сначала я написал этот простой перевод на C ++ алгоритма, описанного выше.Поиск самой правой неминимальной части и распределение значений по композиции выполняется двумя вспомогательными функциями.Код следует шаг за шагом к объяснению, но это не самый эффективный способ его кодирования.Смотрите далее ниже для улучшенной версии.

#include <iostream>
#include <iomanip>
#include <vector>

void DisplayComposition(const std::vector<unsigned int>& comp)
{
    for (unsigned int i = 0; i < comp.size(); i++)
        std::cout << std::setw(3) << comp[i];
    std::cout << std::endl;
}

void Distribute(std::vector<unsigned int>& comp, const unsigned int part, const unsigned int max, unsigned int value) {
    for (unsigned int p = part; value && p < comp.size(); ++p) {
        while (comp[p] < max) {
            ++comp[p];
            if (!--value) break;
        }
    }
}

int FindNonMinPart(const std::vector<unsigned int>& comp, const unsigned int part, const unsigned int min) {
    for (int p = part; p >= 0; --p) {
        if (comp[p] > min) return p;
    }
    return -1;
}

void GenerateCompositions(const unsigned n, const unsigned len, const unsigned min, const unsigned max) {
    if (len < 1 || min > max || n < len * min || n > len * max) return;
    std::vector<unsigned> comp(len, min);
    Distribute(comp, 0, max, n - len * min);
    int part = 0;

    while (part >= 0) {
        DisplayComposition(comp);
        if ((part = FindNonMinPart(comp, len - 1, min)) == len - 1) {
            unsigned int total = comp[part] - min;
            comp[part] = min;
            while (part && (part = FindNonMinPart(comp, part - 1, min)) >= 0) {
                if ((len - 1 - part) * (max - min) > total) {
                    --comp[part];
                    Distribute(comp, part + 1, max, total + 1);
                    total = 0;
                    break;
                }
                else {
                    total += comp[part] - min;
                    comp[part] = min;
                }
            }
        }
        else if (part >= 0) {
            --comp[part];
            ++comp[part + 1];
        }
    }
}

int main() {
    GenerateCompositions(15, 4, 3, 5);

    return 0;
}

---

Улучшенный пример кода

На самом деле большинство вызовов FindNonMinPart не нужны, потому что после перераспределения значений,Вы точно знаете, где находится самая правая неминимальная часть, и нет необходимости искать ее снова.Перераспределение дополнительного значения также может быть упрощено без необходимости вызова функции.

Ниже приведена более эффективная версия кода, которая учитывает эти вещи.Он идет влево и вправо по частям, ищет неминимальные части, перераспределяет дополнительные ценности и выводит композиции, как только они будут завершены.Это заметно быстрее, чем в первой версии (хотя звонки на DisplayComposition, очевидно, занимают большую часть времени).

#include <iostream>
#include <iomanip>
#include <vector>

void DisplayComposition(const std::vector<unsigned int>& comp)
{
    for (unsigned int i = 0; i < comp.size(); i++)
        std::cout << std::setw(3) << comp[i];
    std::cout << std::endl;
}

void GenerateCompositions(const unsigned n, const unsigned len, const unsigned min, const unsigned max) {

    // check validity of input
    if (len < 1 || min > max || n < len * min || n > len * max) return;

    // initialize composition with minimum value
    std::vector<unsigned> comp(len, min);

    // begin by distributing extra value starting from left-most part
    int part = 0;
    unsigned int carry = n - len * min;

    // if there is no extra value, we are done
    if (carry == 0) {
        DisplayComposition(comp);
        return;
    }

    // move extra value around until no more non-minimum parts on the left
    while (part != -1) {

        // re-distribute the carried value starting at current part and go right
        while (carry) {
            if (comp[part] == max) ++part;
            ++comp[part];
            --carry;
        }

        // the composition is now completed
        DisplayComposition(comp);

        // keep moving the extra value to the right if possible
        // each step creates a new composition
        while (part != len - 1) {
            --comp[part];
            ++comp[++part];
            DisplayComposition(comp);
        }

        // the right-most part is now non-minimim
        // transfer its extra value to the carry value
        carry = comp[part] - min;
        comp[part] = min;

        // go left until we have enough minimum parts to re-distribute the carry value
        while (part--) {

            // when a non-minimum part is encountered
            if (comp[part] > min) {

                // if carry value can be re-distributed, stop going left
                if ((len - 1 - part) * (max - min) > carry) {
                    --comp[part++];
                    ++carry;
                    break;
                }

                // transfer extra value to the carry value
                carry += comp[part] - min;
                comp[part] = min;
            }
        }
    }
}

int main() {
    GenerateCompositions(15, 4, 3, 5);

    return 0;
}

Answer 2

Этот алгоритм может быть очень легко реализован с использованием поиска в глубину и рекурсивного алгоритма. Поскольку вы не можете использовать рекурсию, вы можете использовать стек для имитации вызовов функций.

Вот одно из возможных решений:

void GenCompositions(
    unsigned int value,
    const unsigned int CompositionLen,
    const unsigned int min,
    const unsigned int max
) {
    using composition_t = std::vector<int>;
    using stackframe = std::pair<composition_t::iterator, unsigned int>;

    // Create a vector with size CompositionLen and fill it with the
    // minimum allowed value
    composition_t composition(CompositionLen, min);

    // Because we may have initialised our composition with non-zero values,
    // we need to decrease the remaining value
    value -= min*CompositionLen;

    // Iterator to where we intend to manipulate our composition
    auto pos = composition.begin();

    // We need the callstack to implement the depth first search in an
    // iterative manner without searching through the composition on
    // every backtrace.
    std::vector<stackframe> callstack;

    // We know, that the composition has a maximum length and so does our
    // callstack. By reserving the memory upfront, we never need to
    // reallocate the callstack when pushing new elements.
    callstack.reserve(CompositionLen);

    // Our main loop
    do {

        // We need to generate a valid composition. To do this, we fill the
        // remaining places of the composition with the maximum allowed
        // values, until the remaining value reaches zero
        for(
            ;
            // Check if we hit the end or the total sum equals the value
            pos != composition.end() && value > 0;
            ++pos
        ) {
            // Whenever we edit the composition, we add a frame to our
            // callstack to be able to revert the changes when backtracking
            callstack.emplace_back(pos, value);

            // calculate the maximum allowed increment to add to the current
            // position in our composition
            const auto diff = std::min(value,max-*pos);

            // *pos might have changed in a previous run, therefore we can
            // not use diff as an offset. Instead we have to assign
            // the correct value.
            *pos = min+diff;
            // We changed our composition, so we have to change the
            // remaining value as well
            value -= diff;
        }

        // If the remaining value is zero we got a correct composition and
        // display it to std::out
        if(value == 0) {
            DisplayVector(
                composition,
                std::distance(composition.begin(), pos),
                min
            );
        }

        // This is our backtracking step. To prevent values below the
        // minimum in our composition we backtrack until we get a value that
        // is higher than the minimum. That way we can decrease this value
        // in the last step by one. Because our for loop that generates the
        // valid composition increases pos once more before exit, we have to
        // look at (pos-1).
        while(*(pos-1) <= min) {
            // If our callstack is empty, we can not backtrack further and
            // terminate the algorithm
            if(callstack.empty()) {
                return;
            }
            // If backtracking is possible, we get tha last values from the
            // callstack and reset our state
            pos = callstack.back().first;
            value = callstack.back().second;
            // After this is done, we remove the last frame from the stack
            callstack.pop_back();
        }

        // The last step is to decrease the value in the composition and
        // increase the remaining value to generate the next composition
        --*(pos-1);
        ++value;
    } while(true);
}

Я также изменил интерфейс DisplayVector, вот возможная реализация:

// Because we stop stepping deeper in our DFS tree, if the remaining value
// is zero, the composition may have wrong values behind pos. This is no
// problem for us, because we know these values have to be the minimum
// allowed value.
void DisplayVector(const std::vector<int>& vector, size_t pos, int minval) {

    // I prefere to print opening an closing brackets around sequences
    std::cout << "{ ";
    // The ostream_iterator is a addition, that comes with C++17.
    std::ostream_iterator<int> out_it (std::cout, " ");
    // If you can't use C++17, you can use a for loop with an index
    // from 0 to pos to print from the composition
    std::copy_n(vector.begin(), pos, out_it);
    // And a for loop to print vector.size() - pos times the value of minval
    // to fill the rest of your composition
    std::fill_n(out_it, vector.size() - pos, minval);
    std::cout << "}\n";
}

Для компиляции этого кода вам нужно установить стандарт на C ++ 17 и включить следующие заголовки:

#include <iostream>
#include <vector>
#include <iterator>

GenCompositions() не использует функции C ++ 17, поэтому, если вы не можете использовать современный компилятор, вы можете переопределить функцию печати и продолжить.