一个很弱智的问题

  1. 去年
    去年含碳碱基 重新编辑

    首先是这样一个问题:
    假设有m个没有区别的球要放到n个有区别的盒子里,每个盒子可以放任意个球(包括0个),求所有可能的放法。
    注意是“写出所有可能的放法”,不是求有多少种放法

    为了解决这个问题,一个比较自然的思路就是,对于每一个球而言,都有n种放法,这些放法可以用一个n*n的单位矩阵来表示:
    \(\begin{matrix}
    1 & 0 & ...& 0\\
    0 & 1 & ...&0 \\
     0& 0& ...&0 \\
     & ...& ...& \\
     0& 0 & ...&1
    \end{matrix}\)
    对于某一种“放法”,本质上是从这m个n*n单位矩阵中各抽取一个行向量,加和之后的向量即为一种“放法”
    显然,这样求出的放法里面有重复的,但去重对计算机来说也算一个比较简单的过程,因此这个方法还是可行的
    这时,问题转化为“遍历这m个矩阵的所有行向量组合”
    直观上看这应当是个很简单的问题,但是把它写成一个迭代函数似乎不太容易
    以下为我写的解2个球放入3个盒子的方法:

    import numpy as np
    def ball_in_box(ball,box):
        for i in range(0,box):
            a_ball=[[0 for i in range(ball)] for k in range(ball)]
        for i in range(0,ball):
            a_ball[i][i]=1
        methods=[]
        for row1 in a_ball:         #问题在这里
            method=[]
            for row2 in a_ball:
                method=list(np.array(row1)+np.array(row2))
                methods.append(str(method))        
        print(set(methods))                    
    ball_in_box(3,2)

    在这里我手动地把“从每个矩阵中取行向量”的过程写了出来
    但我觉得应该能写出一个函数f,使得执行f(f(n)-1)就能完成这个迭代操作
    求各位大佬指点

  2. tyj518

    2楼 2017年4月11日 优秀回答者

    为啥从球的角度来看呢?直接枚举每个盒子的球数,做个类似于对树的遍历就行了。

  3. @tyj518 为啥从球的角度来看呢?直接枚举每个盒子的球数,做个类似于对树的遍历就行了。

    没明白……可否细说一下

  4. 我是大缺弦

    4楼 2017年4月11日 化学版主
    去年我是大缺弦 重新编辑

    唔。。用 2 楼的思路撸了代码(好像没有直接回复乃的问题?0。0)

    dp = [[[] for y in range(100)] for x in range(100)]                                                                                                  
                                                                                     
    def solve(m, n):                                               
        if n > 0 and len(dp[m][n]) == 0:                                                       
            if n == 1:                                                               
                dp[m][n].append([m])                                                 
            else:                                                                    
                for i in range(m + 1):                                               
                    dp[m][n].extend([[i] + x for x in solve(m - i, n - 1)])          
        return dp[m][n]        
  5. 我是大缺弦

    5楼 2017年4月11日 化学版主
    去年我是大缺弦 重新编辑

    一些讨论见 这里 ,看起来有公式(就是链接里 $N \leq S$ 的情况)

  6. @我是大缺弦 一些讨论见 这里 ,看起来有公式(就是链接里 $N \leq S$ 的情况)

    我要是没理解错的话,链接中的内容是想推导出这种球盒问题的可能性数量的一般公式
    但我穷举这个不是为了得出有多少种,而是为了得到每一个可能的具体形式

  7. 我是大缺弦

    7楼 2017年4月11日 化学版主

    @含碳碱基 我要是没理解错的话,链接中的内容是想推导出这种球盒问题的可能性数量的一般公式
    但我穷举这个不是为了得出有多少种,而是为了得到每一个可能的具体形式

    是的🙈

  8. @我是大缺弦 唔。。用 2 楼的思路撸了代码(好像没有直接回复乃的问题?0。0)

    dp = [[[] for y in range(100)] for x in range(100)] def solve(m, n): if n > 0 and len(dp[m][n]) == 0: if n == 1: dp[m][n].append([m]) else: for i in range(m + 1): dp[m][n].extend([[i] + x for x in solve(m - i, n - 1)]) return dp[m][n]

    这个的确解决问题了,但我还是有点好奇那个n重循环怎么写

  9. 天马行空

    9楼 2017年4月11日 数学版主

    是要对m,n列举出有序m个和为n的数的所有方案?

    def f(m,n):
    	if not m:
    		if not n:
    			yield ()
    		return
    	for i in range(n+1):
    		for j in f(m-1,n-i):
    			yield (i,)+j
  10. 天马行空

    10楼 2017年4月12日 数学版主

    按lz的算法....

    f=lambda m,n:reduce(lambda x,y:set((tuple(map(sum,zip(u,v))) for u in x for v in y)),(tuple(((0,)*i+(1,)+(0,)*(n-i-1)for i in range(n)))for _ in range(m)),{(0,)*n})
  11. 天马行空

    11楼 2017年4月13日 数学版主

    嘛..其实lz要的可能是这个..

    import numpy as np
    def ball_in_box(ball,box):
        for i in range(0,box):
            a_ball=[[0 for i in range(ball)] for k in range(ball)]
        for i in range(0,ball):
            a_ball[i][i]=1
        def _aux(box):
            if not box:
                return [(0,)*ball]
            methods=[]
            for i in _aux(box-1):
                for j in a_ball:
                    method=tuple(np.array(i)+np.array(j))
                    methods.append(method)
            return methods
        return set(_aux(box))
  12. Vacant小星

    12楼 2017年5月9日 数学版主

    你们都用py的呀

  13. @Vacant小星 你们都用py的呀

    是啊
    我不会py,结果ZeroNet是py的,DDCC工具是py的,Waifu2x是py的…… /break

 

后才能发言