将项目重新排列成没有相邻项目的阵列

可以说我有一个块的集合。 12个红色，8个蓝色，5个黄色和1个绿色。我需要创建一个算法，将这些对象输出到一个没有相邻红色块的单个阵列中，相互之间没有蓝色块等。输出应该看起来像这样：将项目重新排列成没有相邻项目的阵列

红色，蓝色，红色，蓝，红，蓝，黄，蓝，绿，红，黄等等。我上一次做这件事大概是在2年前为一家创业公司工作。我在python中实现了这样的算法，但是源代码不可用。我记得我花了至少100条线来创作。

这个算法有一个名字吗？我不想再实施它。

2012-06-14 priestc

我不知道这个问题的名称。下面是我想出来解决它的算法。

你需要跟踪其余各块的＃的。

repeat: 
output 1 block of largest color set. 
output 1 block from the second largest color set.

输出：

rbrbrbrbrgrbrgrbrgrbr grbgy

注：运行该算法之前，你需要检查，看看是否最大的彩色集的大小大于1 +总和另一种颜色的尺寸。如果是这样，就没有解决办法。

注：从第二大集采摘不是必需的。循环中的第二个选择可以来自任何非最大的颜色集。

来源

2012-06-14 20:41:28

这或多或少是我想出来的，除非你不需要从第二高的集合中拉出，只能从任何“非最高”集合中拉出。 – priestc

@ nwv4你是对的！ –

@priestc我认为专门治疗第二个最频繁的设置是必要的。例如'r r r r g b w c c c'，如果我们在'r r r r'的填充时使用'g b w'，那么我们就剩下所有'c c c'，这是不需要的。 – lcn

只是把我的头顶部的 - 创建一个包含所有要在减少数量插入块队列（即使用队列上面的例子中会包含12个红色则8个蓝色然后5个黄色则1个绿）。将队列中的元素插入数组的每个偶数索引，然后插入每个奇数索引（即在索引处插入一个红色块 0,2,4,6,8,10,12,14,16,18,20,22 ，然后在24,1,3,5,7,9,11,13插入布鲁斯则在15,17,19,21插入黄色和23插入绿色）

注意，对于这个区块的一些组合任务是不可能的 - 在运行算法之前，您必须检查具有最高编号的块的集合不再具有比除以2的所有块的总和还要多的块。

来源

2012-06-14 20:06:51 user1440922

你的例子是错误的。你列出有13个红色块。如果有12/8/8/8块，你的算法也有问题。 –

首先你需要检查这样的数组是否存在。

例如如果你有4个红色和1只蓝色的，那么它不存在

所以，如果最大的集数是比其他所有的藏品减1之和的情况，那么就没有有效的解决方案
然后，您只需将所有最大集合中的所有项目（例如红色）都列为列表。

列表中的每个项目之间，它是一个点，你可以插入其他元素
```
e.g. _ red _ red _ red _ red _ red _ red ... 
```
现在，你可以通过收集插入其他物品收集到那些景点。收藏的顺序无关紧要。
```
e.g. blue red blue red blue red blue red yellow red yellow red _ red _ red .. 
```
您需要始终从左向右消耗这些斑点（或始终从右向左）。

每当你用光点时，你再次从左边（或右边）开始插入物品到新点。
```
e.g. green blue _ red _ blue _ red _ blue _ red _ blue _ red _ yellow _ red ... 
```

来源

2012-06-14 21:12:55 xvatar

你的回答会说集合3-red 2-blue（3！<2-1）无法解决。显然这是错误的：因为数组{红，蓝，红，蓝，红}是一个有效的解决方案。 –

@ColinD不，我的意思是如果它更小，那么没有有效的解决方案..也许我不清楚，只是更新了帖子 – xvatar

将项目重新排列成没有相邻项目的阵列

回答

相关问题