K массив продуктов
Я работаю над проблемой алгоритмов. У вас есть массив чисел, размер массива t , число number_of_elements и значение умножения числа. Вам нужно найти любой набор индексов number_of_elements элементов массива, произведение которых будет равно multiplication_value. Гарантируется, что такой набор индексов существует
Эта проблема выглядит как сумма 2, но я не могу экстраполировать ее на свой случай. Я пробовал наивный алгоритм для O (n), но он терпит неудачу, когда у вас неправильное первое число в массиве. Я думаю, что здесь есть способ использовать рекурсию. Я думаю, это известная проблема, но я не мог найти решение
Пример в:
t = 7
number_of_elements = 2
multiplication_value = 27
numbers = [9,1,1,27,3,27,3]
Выходной пример:
1 3
Мои идеи кода:
def return_index_values(numbers,multiplication_value,number_of_elements):
cur_number = int(multiplication_value)
list_of_indexes = []
values = []
for i in range(len(numbers)):
if ((cur_number == 1) and (len(values) == number_of_elements)):
print(values)
#finishing if everything worked
break
else:
if (cur_number % int(numbers[i]) == 0):
if (len(values) < number_of_elements):
#pushing values if possible
values.append(int(numbers[i]))
list_of_indexes.append(i)
cur_number = int(cur_number / int(numbers[i]))
print(cur_number)
else:
pass
if (len(values) == number_of_elements):
if mult_check(values,int(multiplication_value)):
#mult_check checks if the array's element multiplication gives a value
break
else:
#started dealing with bad cases, but it doesn't work properly
values.sort()
val_popped = values.pop()
cur_number = cur_number * val_popped
Плохой случай для моего кода
numbers = [9,3,1,27,3,27,3]
Ответы 2
Вы можете использовать itertools.combinations() (https://www.geeksforgeeks.org/itertools-combinations-module-python-print-possible-combinations/) для выбора записей number_of_elements из вашего списка всеми возможными способами, а затем проверить каждую, умножаются ли они на требуемое число.
Какова его временная сложность? О (п ^ 2)?
Поскольку это комбинации, будет O(n!)
Вот одна реализация. Не обязательно лучшее решение, но оно дает вам некоторое представление о том, как это можно сделать.
Сначала он сортирует numbers по элементу, хранящему информацию об индексах. Затем он выполняет рекурсивные вызовы.
number_of_elements = 2
multiplication_value = 27
numbers = [9,1,1,27,3,27,3]
def preprocess(numbers, multiplication_value, number_of_elements):
l = []
for i, num in enumerate(numbers):
l.append((num, i))
return sorted(l, key = lambda tup: tup[0])
def subroutine(numbers, multiplication_value, number_of_elements, idx_start, result):
if idx_start >= len(numbers):
return False
if number_of_elements == 0:
return True if multiplication_value == 1 else False
for i in range(idx_start, len(numbers)):
num = numbers[i][0]
if num <= multiplication_value:
if multiplication_value % num == 0:
idx = numbers[i][1]
result.append(idx)
found = subroutine(numbers, multiplication_value / num, number_of_elements - 1, i + 1, result)
if not found:
del result[-1]
else:
return True
else:
return False
return False
result = []
processed_numbers = preprocess(numbers, multiplication_value, number_of_elements)
subroutine(processed_numbers, multiplication_value, number_of_elements, 0, result)
print(result)
@andreee, спасибо, исправила