排列，但保留一些数字的顺序

Question

好的，我已经浏览了一下，我正在寻找这个问题的C或python解决方案。我更喜欢python…尽管它是我较弱的语言（有两种非常弱的语言）。在

一组数字，如0 0 1 7 0 0 3 0 0 4

1. 找到集合的所有排列。在
2. 数字>；0必须按顺序排列（不是位置！）在
3. 数字之间必须有一个0，但是在集合的开始和结尾不需要0。只要数字之间至少有一个0>；0。在

所以，首先，我想找到所有可能的排列，然后去掉谷壳（检查如果n>；0！n+1>；0），然后第一个数字>；0==1，第二个数字0==7等

然后我停了下来，觉得这太蠢了，如果有12个数字，那就是12个！排列。按照5亿个排列顺序排列，我必须再进行一次，以除去谷壳。在

假设我有40-50组这些数字集要经历，那是一个公平的时间。在

有没有更符合逻辑的方法？ 我想让python以某种方式进行排列（如果n>；0，n+1必须==0）和（n=第一个数字，n2=第二个等等）

小集合的一个例子是（不是所有的排列，但给出了一个想法）：

1,2,3,0,0,0,0,0

1. 1,0,2,0,3,0,0,0
2. 0,1,0,2,0,3,0,0
3. 0,0,1,0,2,0,3,0
4. 0,0,1,0,0,2,0,3
5. 0,1,0,0,2,0,3,0

等等。 所以1，2，3是正确的，但是“0”只是左右移动？在

谢谢！在

Answer 1

def find_permutations(l):
    n = [e for e in l if e] # Strip zeros.
    # Interspace non-zeros with zeros.
    m = [j for i in n for j in (i,0)][:-1]
    def fill(m):
        if len(m) == len(l):
            yield tuple(m)
        else:
            # Recursively fill with zeros.
            for i in range(len(m)+1):
                for o in fill(m[:i] + [0] + m[i:]):
                    yield tuple(o)
    return sorted(set(fill(m)))

我想这应该能覆盖它。因此，例如（在python 3中），可以执行以下操作：

^{pr2}$

这和你想的一样吗？在

编辑：基本上，fill函数的作用是在列表的每个数字之间插入一个0，然后递归。只要在fill函数中记录了足够的数字（递归生成的数字的列表长度等于原始输入的列表长度），就会返回一个数字元组。在

返回时转换为元组的唯一原因是类型必须是散列的才能在集合中使用，如find_permutations函数的最后一行所示。sorted表示友好。在

Answer 2

基本上，你想通过根据事物的不变量分组来减少必须计算的组合数。由于非零数必须按固定的顺序排列，所以我们先从这个开始：

   1 2 3

因为它们之间必须有0，所以把它们加进去

^{pr2}$

现在只剩下三个0，你需要计算出有多少个组合给出了不同的序列。很明显，在这个例子中，你可能拥有的位置是：在1之前，在1和2之间，在2和3之间，在3之后。你有4个位置来决定如何拆分剩下的三个0。这是一个combination problem with repetition，这里的解决方案是(3 + 4 - 1) Choose 3（即20）。在

希望我处理这个示例问题的方式足以让你把它推广到任意序列，所以我将把它作为练习留给读者。在