K массив продуктов - PullRequest
Новая
       30

K массив продуктов

1 голос
/ 29 мая 2019

Я работаю над проблемой алгоритмов.У вас есть номера массива, размер массива t, число number_of_elements и число multiplication_value.Вы должны найти любой набор индексов 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 ]

0 голосов
/ 29 мая 2019

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

Сначала сортируется 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)
0 голосов
/ 29 мая 2019

Вы можете использовать itertools.combination () (https://www.geeksforgeeks.org/itertools-combinations-module-python-print-possible-combinations/), чтобы выбрать записи number_of_elements из вашего списка всеми возможными способами, а затем проверить каждую из них, умножаются ли они на требуемое число.

...