排列,但有一些数字保持在一个顺序

Question

好的,我已经浏览了一下,我已经找到了解决这个问题的C或python解决方案.我更喜欢python ...虽然它是我较弱的语言(2种非常弱的语言).

一组数字,例如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!排列.这是500,000,000排列的顺序,我将不得不再次通过以摆脱箔条.

假设我有40到50套这些数字套装可以通过,这是一个公平的时间.

有更合乎逻辑的方式吗？我想到某种方式让python做排列以某种方式考虑这些规则(如果n> 0,n + 1必须== 0)和(n =第一个数字,n2 =第2个等)

一个较小的集合的例子是(不是所有的PERMUTATIONS,但给出了想法):

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

基本上，您希望通过根据事物的不变量进行分组来减少必须计算的组合数量。由于非零数字必须采用固定顺序，让我们从以下开始：

   1 2 3

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

   1 0 2 0 3

现在剩下的就是三个 0 需要放置，并且您需要计算有多少个组合给出了不同的序列。从这个例子中可以清楚地看出，您可能拥有的位置是：1 之前、1 和 2 之间、2 和 3 之间以及 3 之后。您有 4 个位置来决定如何拆分剩余的三个 0。这是一个带有重复的组合问题，其解为(3 + 4 - 1) Choose 3（20）。

希望我解决这个示例问题的方式足以让您将其推广到任意序列，因此我将把它作为练习留给读者。