枚举A盒中N个球的组合? [英] Enumeration of combinations of N balls in A boxes?
问题描述
我想枚举 A 框中的 N 个球的所有可能组合。
I want to enumerate all possible combinations of N balls in A boxes.
示例:
我有 8 个球可以处理 3 框:
example: I have 8 balls to deal in 3 boxes :
box_1 box_2 box_3
case-1 8 0 0
case-2 0 8 0
case-3 0 0 8
case-4 7 1 0
case-5 7 0 1
case-6 6 2 0
...
我的第一个问题是我需要 A 循环来执行此操作,但是我希望 A 和 N 作为用户的输入。那么,如何在不编写用户可能需要的所有可能数量的循环的情况下进行操作呢?
My first problem is that I need A loops to perform this but I want that A and N to be user's inputs. So how to do without writing all possible number of loops users could need?
a 和 N 的值在2到〜800之间,因此对计算时间的要求很高。如何优化该算法?
a and N will be value between 2 and ~800, so it will be strongly demanding in computation time so. How to optimize that algorithm?
如果您使用python语言回答我,我将不胜感激。
感谢您的所有贡献!
I would be grateful if you answer me using python language. thanks for all contributions!
推荐答案
从python 2.6开始,此方法就很好了,(( itertools.permutations
的2.5友好实现。 ):
This works just fine starting with python 2.6, (2.5-friendly implementation of itertools.permutations
is available as well):
>>> import itertools
>>> boxes = 3
>>> balls = 8
>>> rng = list(range(balls + 1)) * boxes
>>> set(i for i in itertools.permutations(rng, boxes) if sum(i) == balls)
{(0, 1, 7), (3, 1, 4), (0, 4, 4), (1, 0, 7), (4, 0, 4), (3, 0, 5), (1, 2, 5), (1, 7, 0), (0, 8, 0), (1, 4, 3), (6, 0, 2), (4, 3, 1), (3, 3, 2), (0, 5, 3), (5, 3, 0), (5, 1, 2), (2, 4, 2), (4, 4, 0), (3, 2, 3), (7, 1, 0), (5, 2, 1), (0, 6, 2), (6, 1, 1), (2, 2, 4), (1, 1, 6), (0, 2, 6), (7, 0, 1), (2, 1, 5), (0, 0, 8), (2, 0, 6), (2, 6, 0), (5, 0, 3), (2, 5, 1), (1, 6, 1), (8, 0, 0), (4, 1, 3), (6, 2, 0), (3, 5, 0), (0, 3, 5), (4, 2, 2), (1, 3, 4), (0, 7, 1), (1, 5, 2), (2, 3, 3), (3, 4, 1)}
这篇关于枚举A盒中N个球的组合?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!