Найдите все комбинации для x ^ n и проверьте, складываются ли они в число, исключая одинаковые числа

Question

Итак, я искал программу, которая просматривает все комбинации индексов массива и проверяет, есть ли в массиве соответствующие числа, которые складываются в определенное число (например, с двумя индексами: массив [от 0 до 10] + массив [от 1 до 10] == число?). Он должен исключать комбинации с одинаковым индексом и предпочтительно также комбинации только с другим порядком (например, только 1,2, а не 2,1). Когда он находит такую ​​комбинацию, он должен сохранить правильные индексы. Мое решение состояло бы в том, чтобы сделать это с for-loop, но тогда мне нужно было бы создать новый for-loop для каждого дополнительного индекса, который был бы очень утомительным в течение приблизительно. 40 показателей. Вот пример на C ++:

//3 indices
for (int i = 0; i < iter - 2 && canWork == false; i++) {
    for (int k = i + 1; k < iter - 1 && canWork == false; k++) {
        for (int l = k + 1; l < iter && canWork == false; l++) {
            if (sizes[i] + sizes[k] + sizes[l] == number) {
                indices[0] = i;
                indices[1] = k;
                indices[2] = l;
                canWork = true;
            }
        }
    }
}

//4 indices
for (int i = 0; i < sizeArray - 3 && canWork == false; i++) {
    for (int k = i + 1; k < sizeArray - 2 && canWork == false; k++) {
        for (int l = k + 1; l < sizeArray -1 && canWork == false; l++) {
            for (int m = l + 1; m < sizeArray && canWork == false; m++) {
                if (array[i] + array[k] + array[l] + array[m] == number) {
                    indices[0] = i;
                    indices[1] = k;
                    indices[2] = l;
                    indices[3] = m;
                    canWork = true;
                }
            }
        }
    }
}

- 2 и -1 после sizeArray и начала с + 1 служат для пропуска одинаковых сумм. Я начинающий программист, поэтому, пожалуйста, прости меня, если код такой плохой. Я также не мог найти что-нибудь относительно этой проблемы, поэтому я спрашиваю здесь.

Answer 1

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

Идея состоит в том, чтобы найтисвязь между проблемой при поиске n индексов и проблемой при поиске n + 1 индексов.

В данном конкретном случае мы можем свести регистр n + 1 к случаю n индексы с использованием следующих наблюдений:

• Есть две возможности: либо комбинация n + 1 индексов, которая удовлетворяет ограничениям, использует самый последний индекс массива, либо нет.В первом случае мы можем найти комбинацию n + 1 индексов, которые суммируются с number, путем поиска n индексов в массиве вплоть до, но исключая последний элемент, который суммируется с number - v, где v является значениемпоследнего элемента в массиве.Если мы не можем найти такую ​​комбинацию (т. Е. Мы находимся во втором случае), то мы можем снова попытаться найти индексы n + 1 в массиве без последнего элемента.
• Не существует комбинацииn указывает, что сумма равна number, если массив содержит менее n элементов.
• Случай n = 1 тривиален: нам просто нужно один раз пройтись по массиву и посмотреть, сможем ли мынайдите одно значение, которое равно числу, которое мы ищем.

Прямая реализация этих наблюдений может выглядеть следующим образом:

#include <algorithm>
#include <iterator>
#include <vector>

/**
 * returns the `number_of_indices` indices of `input_array` for which 
 * the corresponding elements sum to `sum`, or an empty vector if
 * there is no such combination of indices.
 */
std::vector<std::int64_t> find_n_indices_that_sum_to(std::vector<int> input_array, 
                                                     int number_of_indices,
                                                     int sum)
{
    if (number_of_indices == 1)
    {
        // the trivial case, just search for one element equal to `sum`.
        auto const match = std::find(std::cbegin(input_array),
                                     std::cend(input_array),
                                     sum);

        return match != std::cend(input_array) 
            ? std::vector<std::int64_t>{std::distance(std::cbegin(input_array), match)}
            : std::vector<std::int64_t>{};
    } else if (static_cast<std::size_t>(number_of_indices) > std::size(input_array)) {
        // not enough elements to find the required number of indices
        return std::vector<std::int64_t>{};
    } else {
        auto const last_index = std::size(input_array) - 1;
        auto const value = input_array.back();

        // reduce the size of the array by 1 - either we find
        // `number_of_indices - 1` additional indices that sum to 
        // `sum - value` or we're in case 2 described above and try 
        // to find `number_of_indices` indices in the smaller array
        input_array.pop_back();

        auto indices = find_n_indices_that_sum_to(input_array,
                                                  number_of_indices - 1, 
                                                  sum - value);
        if (!indices.empty()) {
            // case 1 - there is a combination of indices whose corresponding
            //          elements sum to `sum` with one of them being the
            //          very last index of the array
            indices.push_back(last_index);

            return indices;                 
        } else {
            // case 2 - we try again in the smaller array
            return find_n_indices_that_sum_to(input_array,
                                              number_of_indices,
                                              sum);
        }
    }
}

Вы также можете попробовать эторешение на wandbox .

Если хотите, вы можете также попытаться улучшить производительность этого решения, например, заменив векторный аргумент input_array на gsl::span, чтобы избежать копирования илиделая функцию хвостовой рекурсивной или даже полностью императивной, чтобы избежать переполнения стека для больших number_of_indices.