子集和算法从JavaScript到Python的转换

Question

我在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之外，我不想导入任何其他模块。

翻译的地方出了什么问题？

Answer 1

这里有各种各样的问题。

• 永远不要覆盖建筑。Python定义了min、next和list。如果您覆盖它们，您可能会遇到非常微妙的bug。
• Python没有数组，它有列表。永远不要缓存对len的调用--这段代码不会更新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则将空列表视为falsey。min = []不捕获隐式设置min = undefined的原始JS代码，因此if not min检查min是空还是空，这与原始JS版本是不可比拟的。
• 不需要检查类型；检查None或not None就足够了。
• if (next) { if (more stuff ...可以只是使用and的一个块。没有理由去筑巢(这在原来是个问题)。
• 在大多数情况下，使用enumerate而不是range来迭代列表(如果确实使用范围，range(0, len(some_list))可以是range(len(some_list))。
• 坚持佩普-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]