在列表中找到n个整数，使它们相乘等于m。

Question

我需要打印出列表中n个索引的元素，这些元素相乘后等于给定的整数。保证在列表中存在这样的组合。例如，对于以下输入（数组中的元素数量，所需乘积，所需子列表中的元素数量和给定的数组）：

7 60 4 30 1 1 3 10 6 4

我应该以任何顺序得到：

1 2 4 5

因为1 * 1 * 10 * 6 == 60。如果有多个解决方案，我需要打印其中任何一个。我的解决方案有效，但速度很慢，如何使其更快？

from itertools import chain, combinations

arr = list(map(int, input().split()))
numbers = list(map(int, input().split()))

s = sorted(numbers)


def filtered_sublists(input_list, length):
    return (
        l for l in all_sublists(input_list)
        if len(l) == length
    )


def all_sublists(l):
    return chain(*(combinations(l, i) for i in range(len(l) + 1)))


def multiply(arr):
    result = 1
    for x in arr:
        result = result * x
    return result


def get_indexes(data):
    indexes = []

    for i in range(len(data)):
        if arr[1] == multiply(data[i]):
            for el in data[i]:
                if numbers.index(el) in indexes:
                    all_ind = [i for i, x in enumerate(numbers) if x == el]
                    for ind in all_ind:
                        if ind not in indexes:
                            indexes.append(ind)
                            break
                else:
                    indexes.append(numbers.index(el))

            break

    return indexes


sublists = list(filtered_sublists(numbers, arr[2]))

print(*get_indexes(sublists))

- Steve

---

@גלעדברקן n，m，k -（1≤K≤N≤5000，0≤M≤10^9），数组元素 -（0≤Ai≤10^9），很遗憾无法分享测试网页，因为这是一项私人任务。 - Steve

Answer 1

我们可以使用记忆化递归来实现一个 O(n * k * num_factors) 的解决方案，其中 num_factors 取决于我们能够创建多少目标产品的因子。从代码中可以很清楚地看出递归关系。（零值没有被处理，但这些应该很容易添加额外的处理。）

Python风格的JavaScript代码：

function f(A, prod, k, i=0, map={}){
  if (i == A.length || k == 0)
    return []

  if (map[[prod, k]])
    return map[[prod, k]]

  if (prod == A[i] && k == 1)
    return [i]

  if (prod % A[i] == 0){
    const factors = f(A, prod / A[i], k - 1, i + 1, map)
    if (factors.length){
      map[[prod, k]] = [i].concat(factors)
      return map[[prod, k]]
    }
  }

  return f(A, prod, k, i + 1, map)
}

var A = [30, 1, 1, 3, 10, 6, 4]

console.log(JSON.stringify(f(A, 60, 4)))
console.log(JSON.stringify(f(A, 60, 3)))
console.log(JSON.stringify(f(A, 60, 1)))

- גלעד ברקן

---

明天会尝试并反馈结果。 - Steve

@Steve 很酷。我修改并简化了代码，不在映射键中包含 i。 - גלעד ברקן

Answer 2

关键是不要测试每一个组合。

def combo(l, n=4, target=60, current_indices=[], current_mul=1):
    if current_mul > target and target > 0:
        return
    elif len(current_indices) == n and current_mul == target:
        yield current_indices
        return
    for i, val in enumerate(l):
        if (not current_indices) or (i > current_indices[-1] and val * current_mul <= target):
            yield from combo(l, n, target, current_indices + [i], val * current_mul)

l = [30,1,1,3,10,6,4]
for indices in combo(l, n=4, target=60):
    print(*indices)

输出：

1 2 4 5

---

更多测试用例：

l = [1,1,1,2,3,3,9]
for c, indices in combo(l, n=4, target=9):
    print(*indices)

输出：

0 1 2 6
0 1 4 5
0 2 4 5
1 2 4 5

- Andrej Kesely

---

谢谢您的解决方案，它有效，但我仍然遇到了时间限制错误。 - Steve

我不知道输入是什么，但时间限制是1秒，你的解决方案需要1.091秒。 - Steve

没错，但是有一些奇怪的输入/输出标准，所以为了不浪费时间解释，我没有提到那个。因为通常这并不重要，我只是在你的解决方案上加了+1，得到了正确的结果。但是你之前的解决方案仍然存在时间限制的问题。 - Steve

再次在第11个测试中遇到“演示错误”:(很遗憾，我不知道他们在那里使用什么数据作为输入。 - Steve

@Steve 现在我明白可能会出现的问题 - 数组元素可能包含零 (0≤Ai≤10^9)。我编辑了我的答案。 - Andrej Kesely

Answer 3

你可以从目标产品开始，递归地通过剩余列表中的因子进行除法，直到你得到1并使用指定数量的因子。这样做的好处是快速消除不是目标产品因子的递归分支。

在处理列表中的零值和目标产品为零时，需要在开始和遍历因子时设置一些特殊条件。

例如：

def findFactors(product, count, factors, offset=0):
    if product == 0: return sorted((factors.index(0)+i)%len(factors) for i in range(count))  
    if not count: return [] if product == 1 else None
    if not factors: return None
    for i,factor in enumerate(factors,1):
        if factor == 0 or product%factor != 0: continue
        subProd = findFactors(product//factor,count-1,factors[i:],i+offset)
        if subProd is not None: return [i+offset-1]+subProd

r = findFactors(60, 4, [30,1,1,3,10,6,4])
print(r) # [1, 2, 4, 5]

r = findFactors(60, 4, [30,1,1,0,3,10,6,4])
print(r) # [1, 2, 5, 6]

r = findFactors(0, 4, [30,1,1,3,10,6,0,4])
print(r) # [0, 1, 6, 7]

- Alain T.