algorithm - 如何计算有多少个大小为n的位序列(设置了k个位，并且位值发生c次变化)？

我们知道，用k位集计算n个长度的位序列的个数等于c（n，k）=n！/（k！（N-K）！）*.
但我最近问自己，一旦设置了另一个条件：比特值的数量发生变化，您如何考虑这个问题。例如，对于n=4和k=2，我们有6个解：
1-0011号
2-0101号
3-0110年
4-1001个
5-1010年
6-1100个
现在假设我们只想得到位值有两个变化的序列。现在只有两种解决方案：
1-0110（从0开始，更改为1，之后更改为0）。
2-1001（从1开始，更改为0，之后更改为1）。
如何快速计算解的数量（不生成每个组合并计数）？我认为一个人可以把最初的一点算为一个变化，而不必太多地改变答案，所以请随意去做。
额外问题：给定一个k比特集和c比特变化数的组合，用相同的k比特集和c比特变化数生成下一个组合的最快方法是什么？

最佳答案

这是一个balls-and-urns问题您首先将0s和1s与所需的位更改数交替排列，然后将剩余的0s和1s放入urn中。
例如：n=20，k=8，c=4。
考虑一下双字符串以0开头的情况从(c+1)交替位开始，获取您的c更改：

01010

此时您仍然需要放置90s和61s。让我们先放置0s。有多少种方法可以放置剩余的9个0s而不添加任何位更改？有3个“骨灰盒”放置“球”（0s）：

0 ... 1 0 ... 1 0 ...
   ^       ^       ^

将9个球放入3个骨灰盒的方法有多种。
一旦放置了(9+3-1) choose 3s，我们也需要放置0s。通过类似的推理，我们有6个球（1s）放置在2个urn中，这可以通过1的方式来完成。
由于(6+2-1) choose 2s和0s的排列是独立的，因此我们将结果相乘：假设从1开始，一个长度为20位、长度为8((9+3-1) choose 3) * ((6+2-1) choose 2)s的字符串有4位变化的1方法。
您仍然需要添加剩余的案例（从0开始，因此第一步将导致1），这可以用完全相同的方式解决。

关于algorithm - 如何计算有多少个大小为n的位序列(设置了k个位，并且位值发生c次变化)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50615453/