python - Python从一组数字中获取数字

Question

我想知道我可以从一组数字中构建一个数字的次数：

possible_numbers = 1, 2, 4, 8, 16

如果我想要 23 号，我需要

1x 16
0x 8
1x 4
1x 2
1x 1 

Python中是否有任何内置函数可以做到这一点？

编辑：数字固定为 1,2,4,8,16,32,64,128。可以进行多项选择。

由于没有内置函数，我将自己编写代码。

Answer 1

假设可能的数字始终是 2 的幂，您基本上希望将数字转换为二进制格式。这很容易使用内置的bin 功能：

>>> mylist = [int(x) for x in bin(23)[2:]]
>>> print mylist
[1, 0, 1, 1, 1]

要获得与您在问题中显示的完全相同的输出：

>>> for i, j in enumerate(mylist):
...     print '%ix %i' % (j, 2**(len(mylist)-i-1))
...
1x 16
0x 8
1x 4
1x 2
1x 1

Answer 2

假设您的数字不限于 2 的幂，则此解决方案应该有效。它绝对不是抛光或高效的，但它确实有效。

#!/usr/bin/env python

import sys

def factors(desired, numbers):
    if desired == 0:
        return []
    elif desired < 0:
        return None

    for number in sorted(numbers, reverse=True):
        f = factors(desired - number, numbers)
        if f is not None:
            f.append(number)
            return f


if __name__ == "__main__":
    n = int(sys.argv[1])
    possibles = map(int, sys.argv[2].split())
    f = factors(n, possibles)
    print f

    for i in sorted(possibles, reverse=True):
        print "{0}x {1}".format(f.count(i), i)

这里有些例子：

$ python test.py 23 "1 2 4 8 16"
[1, 2, 4, 16]
1x 16
0x 8
1x 4
1x 2
1x 1

$ python test.py 23 "1 2 5 8 16"
[2, 5, 16]
1x 16
0x 8
1x 5
1x 2
0x 1

$ python test.py 23 "1 2 3 8 16"
[1, 3, 3, 16]
1x 16
0x 8
2x 3
0x 2
1x 1

$ python test.py 23 "1 2 3 8 17"
[3, 3, 17]
1x 17
0x 8
2x 3
0x 2
0x 1

Answer 3

如果不允许重复，则有一种使用 powerset 的巧妙方法（以及从http://rosettacode.org/wiki/Power_set#Python抄录的一个不错的 powerset 函数）：

def list_powerset(lst):
    return reduce(lambda result, x: result + [subset + [x] for subset in result], lst, [[]])

def powerset(s):
    return frozenset(map(frozenset, list_powerset(list(s))))

def valid_combos(num, lst):
    return filter(lambda x: sum(x) == num, powerset(lst))

这仅在数字只出现一次时才有效，但我仍然认为这是一个有趣的解决方案。:)