Комбинации выражений с 4 элементарными операциями

Question

Я не мог придумать лучшего названия, для адекватного может потребоваться полное объяснение. Кроме того, комбинации могут вводить в заблуждение, поскольку проблема будет включать перестановки.

Что я хочу сделать sh - это превзойти метод грубой силы в Python при следующей задаче: учитывая 4 элементарных операции [+, -, *, /] и цифры от 1 до 9, и с учетом всех возможных комбинаций из 5 цифр и 4 операций без повторения (перестановок), которые приводят к заданному числу (рассматривается как целое число), как в 1 + 5 * 9-3 / 7 = 45, 1-2 / 3 + 9 * 5 = 45, ... получить все целые числа от минимально возможного до максимально возможного значения и выяснить, существуют ли все целые числа в пространстве.

Моя предварительная попытка с грубым перебором force это следующее:

def brute_force(target):
    temp = 0
    x = [i for i in range(1,10)]
    numbers = [str(i) for i in x]
    operators = ["+","-","*","/"]
    for values in permutations(numbers,5):
        for oper in permutations(operators):
            formula = "".join(o + v for o,v in zip([""]+list(oper),values))
            if round(eval(formula)) == int(target):
                temp += 1
    if temp > 0:
        return True
    else:
        return False

for i in range(-100,100):
    total = brute_force(i)
    if total:
        print(i)
    else:
        print(str(i) + 'No')

Он просто печатает «Нет», кроме целых чисел, которые не были найдены. Как может показаться очевидным, все целочисленные значения можно найти в пространстве, в диапазоне от -71 до 79.

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

Answer 1

Давайте вычислим набор возможных результатов только один раз (и немного проще и быстрее):

expression = [None] * 9
results = {eval(''.join(expression))
           for expression[::2] in permutations('123456789', 5)
           for expression[1::2] in permutations('+-*/')}

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

Используя этот набор результатов, мы можем затем ответить на вопросы мгновенно , подтверждая ваш диапазон и показывает, что отсутствуют только -70 и 78:

>>> min(results), max(results)
(-70.71428571428571, 78.83333333333333)

>>> set(range(-70, 79)) - results
{-70, 78}

Answer 2

Прежде всего, давайте посмотрим на выражение аналитически. У вас есть три условия: произведение P (A * B), частное Q (A / B) и скаляр S. Вы комбинируете их с добавлением и вычитанием.

Два условия являются положительными; другой является отрицательным, поэтому мы можем просто отменить одно из трех слагаемых (P, Q, S) и взять сумму. Это сокращает комбинаторику.

Умножение коммутативно; Wlog, мы можем предположить, что A> B, который сокращает перестановки в два раза.

Вот мое предложение для первой эффективности:

• Сначала выберите условия продукта с A> B ; 36 комбинаций
• Затем выберите S из оставшихся 7 цифр; 7 * 36 = 252 комбинации
• Начиная с последних 6 цифр возможные коэффициенты варьируются от менее 1 до max_di git / min_di git. Сгруппируйте их в классы эквивалентности (один набор для сложения, один для вычитания), вместо того, чтобы проходить все 30 перестановок. Это дает нам примерно 6 значений в каждом случае; теперь у нас есть ~ 1500 комбинаций из трех слагаемых.
• Для каждой из этих комбинаций у нас есть 3 возможных варианта, от которых можно отказаться; общая сумма составляет ~ 4500 сум.

Этого достаточно для улучшения?

---

Спасибо Heap Overflow за указание пропущенного случая с данными (это профессионально неловко :-)).

Дело A * B / C + DE не рассматривается выше. Подход сопоставим.

• Сначала выберите условия продукта с A> B; 36 комбинаций
• Затем выберите C из оставшихся 7 цифр; 7 * 36 = 252 комбинации
• Всего 38 всего возможных коэффициентов; вы можете генерировать их, как вы, с помощью sh, но с таким небольшим количеством комбинаций, грубая сила также разумна.
• Из последних 6 цифр у вас есть 30 комбинаций, но половина из них является отрицанием другой половина. Выберите D> E, чтобы начать, и просто сделайте второй проход для отрицательных. Не пытайтесь проверять наличие дублирующихся различий; это не стоит времени.
• Теперь у вас есть менее 38 коэффициентов для объединения с количеством различий (минимум 5, максимум 8, значит почти 7).

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

Если вам разрешено включать этот анализ в код, вы можете сократить эту часть, изменив поиск. Вы демонстрируете охват больших дел {48, 54, 56, 63, 72}, демонстрируете заполнение пробелов для меньших коэффициентов, а затем вы можете искать с меньшими сложностями случаи в моей первоначальной публикации, наслаждаясь знанием того, что вы нужно только 78, 79 и цифры меньше -8.

Answer 3

Я думаю, вам просто нужно найти перестановки ОДИН РАЗ. Создайте набор из всех возможных сумм. А потом просто сделай поиск. Все еще своего рода грубая сила, но экономит много повторных расчетов.

def find_all_combinations():
    x = [i for i in range(1,10)]
    output_set = set()
    numbers = [str(i) for i in x]
    operators = ["+","-","*","/"]
    print("Starting Calculations", end="")
    for values in permutations(numbers,5):
        for oper in permutations(operators):
            formula = "".join(o + v for o,v in zip([""]+list(oper),values))
            # Add all the possible outputs to a set
            output_set.add(round(eval(formula)))
            print(".", end="")
    return output_set

output = find_all_combinations()

for i in range(-100,100):
    if i in output:
        print(i)
    else:
        print(str(i) + 'No')