时间戳

首页 > 解决方案 > 将子集和算法从 JavaScript 转换为 Python

javascript - 将子集和算法从 JavaScript 转换为 Python

问题描述

我在 JavaScript 中有以下代码来计算数组中总和等于的最小元素n：

function findMinSum(arr, n){
    if(!arr) return 
    let min 
    for (let i=0; i<arr.length; i++) {

        /* if a number equals the sum, it's obviously
         * the shortest set, just return it
         */
        if (arr[i] == n) return [arr[i]]     

        /* recursively call on subset with
         * sum adjusted for removed element 
         */
        let next = findMinSum(arr.slice(i+1), n-arr[i])

        /* we only care about next if it's shorter then 
         * the shortest thing we've seen so far
         */
        if (next){
            if(min === undefined || next.length < min.length){
                min = [arr[i], ...next]
            }
        }
    }
    return min && min  /* if we found a match return it, otherwise return undefined */
}

我从这里得到了这个代码。

我想将其转换为 Python，所以我做了以下操作：

def findMinSum(arr, n):
    if not arr:
        return

    min = []
    min_len = len(min)
    for i in range(0, len(arr)):

        if(arr[i] == n):
            return (arr[i])

        next = []
        next = findMinSum(arr[i+1:], n-arr[i])

        if(next == list):
            next_len = len(next)
        else:
            next_len = next

        if(next):
            print(next) # printing next for debugging purpose 
            if( ( not min ) or (next_len < min_len) ):
                min = [ next, arr[i]]

    return min

arr = [8, 6, 1, 5, 9, 3]
get_min = findMinSum(arr, 14)

print(get_min)

但是当我运行这段代码时，我收到以下错误：

3
[3, 1]
9
[[3, 1], 6]
3
[3, 9]
Traceback (most recent call last):
  File "test1.py", line 34, in <module>
    min2 = findMinSum(arr, 14)
  File "test1.py", line 25, in findMinSum
    if( ( not min ) or (next_len < min_len) ):
TypeError: '<' not supported between instances of 'list' and 'int'

预期的输出应该是[8, 6]或[9, 5]。

我想不出任何其他方式来编写代码，因为我是 Python 的新手。此外，我不想导入除 numpy 之外的任何其他模块。

我在哪里翻译错了？

标签： javascriptpythonpython-3.xlist

解决方案

这里有各种各样的问题。

  • 永远不要覆盖内置函数。Python 定义min,next和list. 如果你覆盖它们，你可能会遇到非常微妙的错误。
  • Python 没有数组，它有列表。永远不要缓存对len--this code doesn't update的调用，因此如果曾经更新min_len = len(min)，该值在此循环中的未来比较中是陈旧的。min
  • 避免在条件和返回语句周围使用不必要的括号，因为括号用于创建元组。return (arr[i])应该是return [arr[i]]（单个元素列表）。
  • min = [ next, arr[i]][arr[i], ...next]在排序或拆包/传播方面都不匹配。min = [arr[i], *next]用来压扁next。
  • JS 和 Python 以不同的方式处理undefined/None和布尔数组/列表值。JS 将空数组视为真，而 Python 将空列表视为假。min = []不捕获min = undefined隐式设置的原始 JS 代码，因此if not min检查是否min为 null或 empty，这与原始 JS 版本无法比较。
  • 无需检查类型；检查Noneornot None就足够了。
  • if (next) { if (more stuff ...可以只是一个块使用and. 没有理由嵌套（这是原来的问题）。
  • 在大多数情况下，使用enumerate而不是range迭代列表（如果你使用范围，range(0, len(some_list))可以是range(len(some_list)).
  • 遵守PEP-8。用于snake_case函数和变量名称。

这是我的重写：

def find_smallest_sum(lst, n):
    if not lst:
        return None

    smallest = None

    for i, e in enumerate(lst):
        if e == n:
            return [e]

        next_lst = find_smallest_sum(lst[i+1:], n - e)

        if next_lst is not None and (smallest is None or len(next_lst) < len(smallest)):
            smallest = [e, *next_lst]

    return smallest

if __name__ == "__main__":
    print(find_smallest_sum([10, 0, -1, 20, 25, 30], 59))  # => [10, -1, 20, 30]
    print(find_smallest_sum([8, 6, 1, 5, 9, 3], 14))       # => [5, 9]

推荐阅读