求助万能的 V 友一个排序问题

[nevin47]

最近做一个算法脑袋短路卡了半天了，其实不能严格说是一个排序问题

大致问题如下：
有一串数组：0 0 0 0 0... 0 0 0（n个0）
现在插入1~n个1进去
如：插入一个1
1 0 0... 0 0 0
0 1 0... 0 0 0
...
0 0 0... 0 0 1
插入两个1
1 1 0... 0 0 0
1 0 1... 0 0 0
...
0 0 0... 0 1 1
求所有情况

万能的V友能给个解决思路么

[Gonster]

这是数学问题C n+1, 2

[batman2010]

把数组视为一个二进制数，之后做二进制减法。不过，这样的话顺序就和你给的有点不一样了。

[nevin47]

@batman2010 好像是个思路！我试试python二进制减法怎么做
顺序其实无所谓的，只要把所有情况求出来就行了

[Gonster]

刚刚说错了....

如果如果只是求没每种插入的组合数 那么n个零插入k个1号最后会有n+k位
从n+k个位置中选出k个放1
组合数为C(n+k,k)

[theFool]

@Gonster
不对吧。0110 比如这样的你算两遍了。
个数应该为(n+1)^k吧。

[Gonster]

@theFool 你说的0110号 n=2 k=2
C(2+2,2)=4*3/2=6
1100 1010 1001 0110 0101 0011

[theFool]

@Gonster 不要理我。。组合数弄错了。。sorry sorry.

[linhua]

分析一下：输入两个参数，循环嵌套数目（乘号数目）取决于k，估计要用到递归。
如有不正，请指出。

[Gonster]

win8.1自带的输入法怎么这么诡异 .... 输入数字以后按空格一定会补一个号字....

[comicfans44]

如果不要求顺序的话
这不就是把 000到 111 所有二进制数字列一遍吗...

000
001
010
100
101
110
111

所有情况就是 2^n次方

[linxy]

设F(i)为插入第i个时的情况总数
有F(i)=F(i-1)×(C (1,n+i+1) / i ! )
以上
如果是要输出所有的情况…我再想想

有误之处请指正

[comicfans44]

...少写了一个011

[linxy]

对了，上面i不等1.因为没有定义0个1插入并没有实际意义

[linxy]

不对，递推式要有个初值才行，实际上还要给出F(0)=1

[liuhaotian]

恩 @Gonster 的这个是对的... 半年不做数学题了，差点连这道题也解不来

[black]

是插入吧？n 个 0, 插入 m 个 1 的话，可能的组合是 C(n + m, m)，m是上标

[black]

另外我觉得既然限定条件 1~n 个1，那么这题可能不是 “插入”，而是将 n 个 0 的某 m 位 “置为” 1，如果是这种情况，那么可能的组合数是 C(n, m)，m是上标

[nevin47]

居然好多V友帮忙回复
此问题已经解决，因为无所谓具体顺序，就是按照@batman2010 给的思路做了一个递减转二进制然后转List搞定

再次感谢大家~要是有好的想法还可以再继续交流哈哈

[nevin47]

@black 对的，不是插入。是生成