在A盒中枚举N球的组合？

发布时间：2020-12-20 12:35:52 所属栏目：Python 来源：网络整理

导读：我想列举A盒中N球的所有可能组合. 例：我有8个球可以处理3个盒子： box_1 box_2 box_3case-1 8 0 0case-2 0 8 0case-3 0 0 8 case-4 7 1 0case-5 7 0 1case-6 6 2 0... 我的第一个问题是我需要A循环来执行此操作,但我希望A和N是用户的输入.那么如何在不编写

我想列举A盒中N球的所有可能组合.

例：
我有8个球可以处理3个盒子：

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是用户的输入.那么如何在不编写用户可能需要的所有可能数量的循环的情况下做到

a和N的值在2到800之间,因此计算时间要求很高.如何优化该算法？

如果你用python语言回答我,我将不胜感激.
感谢所有的贡献！

解决方法

伪代码：

Enumerate(Balls,Boxes)
  if Boxes<=0 
    Error
  elseif Boxes=1 
    Box[1] = Balls
    PrintBoxes
  else
    forall b in 0..Balls 
      Box[Boxes] = b
      Enumerate(Balls-b,Boxes-1)
    endfor
  endif
end

说明

从第一个框开始,如果没有框,则抱怨并退出.
如果它是要填充的最后一个框,则丢弃所有剩余的球并显示结果.
如果有更多的盒子,首先添加0个球并与其他盒子重复该过程.然后加1球2球直到没有球.

为了表明该算法有效,我给出了一个实际值,3个球和2个盒子的例子.

我们有一个名为Box的盒子阵列,每个盒子可以容纳任意数量的球(值). PrintBoxes打印框的当前值.

Box = (0,0)
Enumerate(3,2)
  b=0
  Box = (0,0)
  Enumerate(3,1)
    Box = (3,0) 
    Print!
  b=1 
  Box = (0,1)
  Enumerate(2,1)
    Box = (2,1)
    Print!
  b=2
  Box = (0,2)
  Enumerate(1,1)
    Box = (1,2)
    Print!
  b=3   
  Box = (0,3)
  Enumerate(0,1)
    Box = (0,3)
    Print!

 Output:

 (3,0)
 (2,1)
 (1,2)
 (0,3)

 Which are all the combinations.

另一个有3个盒子和3个球的例子：

Box = (0,3)
  b=0
  Box = (0,2)
    b=0
    Box = (0,0)
    Enumerate(3,1)
      Box = (3,0)
    b=1
    Box = (0,1,0)
    Enumerate(2,1)
      Box = (2,0)
    b=2
    Box = (0,2,0)
    Enumerate(1,1)
      Box = (1,0)
    b=3
    Box = (0,3,0)
    Enumerate(0,1)
      Box = (0,0)
  b=1 
  Box = (0,1)
    Enumerate(2,1)
    b=1
    Box = (0,1)
    Enumerate(1,1)
    b=2
    Box = (0,1)
    Enumerate(0,1)
  b=2
  Box = (0,2)
    Enumerate(1,2)
    b=1
    Box = (0,2)
    Enumerate(0,2)
  b=3   
  Box = (0,3)
    Enumerate(0,3)

Output
(3,0)
(2,0)
(1,0)
(0,1)
(1,1)
(0,2)
(0,3)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!