Эффективная помощь в кодировании

Question

В настоящее время я пишу код на C ++, чтобы найти все возможные перестановки из 6 целых чисел и сохранить наилучшую перестановку (т. Е. Ту, сумма которой ближе всего к данному значению).

Я пытаюсь написать этот код максимально эффективно и буду признателен за любые советы или примеры.

Я думал о сохранении целых чисел в массиве и выполнении перестановок с использованием указателей внутри цикла. Это хороший подход?

Answer 1

Они уже подумали об этом для вас:

#include <algorithm>

int ra[6] = { 1, 2, 3, 4, 5, 6 };

do {
    // whatever
} while (std::next_permutation(ra, ra+6));

Обратите внимание, что элементы должны начинаться в порядке возрастания (путем сравнения через оператор <), иначе цикл завершится до того, как вы увидите каждую перестановку. Подробнее см. <a href="http://en.cppreference.com/w/cpp/algorithm/next_permutation" rel="nofollow noreferrer">http://en.cppreference.com/w/cpp/algorithm/next_permutation.

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

Answer 2

Взгляните на этот замечательный пост @ Кодирование колеса : Исчерпывающее перечисление комбинаций и перестановок в коде . Он имеет полный код и был написан сотрудником SO'r , этого должно быть достаточно, чтобы вы встали на правильный путь.

Answer 3

Предполагая, что дублированные номера не являются проблемой, их n! перестановки из n целых чисел (взятых по n за раз). Поэтому независимо от того, что вы делаете, ваш алгоритм будет иметь факториальное временное поведение (O (n ^ n)).

Другими словами, когда n становится большим, оно будет медленным . К сожалению.

На самом деле, на странице википедии есть алгоритмы для этого.

Answer 4

Я думал о сохранении целых чисел в массиве и выполняя перестановки с использованием указателей в пределах петля. Это хороший подход?

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