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

繰り返しが許可されていない場合は、パワーセットを使用する適切な方法があります (およびhttp://rosettacode.org/wiki/Power_set#Pythonから引用された優れたパワーセット関数):

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))

これは、数値が 1 回しか表示されない場合にのみ機能しますが、それでも楽しい解決策だと思います。:)