8张扑克牌问题
1、问题描述
有8张扑克牌，两张1，两张2，两张3，两张4。现在需要排序成一排，要求每张牌号为1的牌中间间隔1张牌，每张牌号为2的牌间隔2张牌，每张牌号为3的牌间隔3张牌，每张牌号为4的牌间隔4张牌，请问有几种放置方案？
例如如下排列不符合规范，因为位置6和位置7放置的两张4中间没有间隔4张牌。
| 位置1 | 位置2 | 位置3 | 位置4 | 位置5 | 位置6 | 位置7 | 位置8 |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 1 | 3 | 2 | 4 | 4 | 3 |
2、分析与陈述
该问题实际想问如何将8个数字进行排列，从而满足特性的间隔要求。
问题输入为8个数字，输出为8个已经排序的数组，操作环节只有排序。
3、问题分解方案1–穷举法
观点：只需按要求将前四个位置，按照牌的摆放要求填满前4位，则如果8个位置都是满的，则符合题目要求。
复杂度：第一个位置可能性8，第二个位置可能性7，则遍历方全部案需要8 * 7 * 6 * 5 ，复杂度为n!，典型NP问题。类似于算法中的TSP 旅行推销商问题。
结论：放弃。
4、问题分解方案2–贪心算法
观点：题目可以分解为如何放置4对牌可以填满8个问题。即共有4个子问题：两张1的放置，两张2的放置……。类似于零钱兑换问题。
第一次选择放置两张4，因为4的确定性最高，后续选择可能性也就越少，共有3种放置方案。
第二次放置两张3，每种都是两种放置方案。
……
选择次数：3 * 2 * 2。
结论：41312432、23421314
5、类比
类比观点：每对牌有固定间隔，类似于三维世界的体积；占满8个位置类似于填满固定空间。那么类比于如何将鸡蛋、大枣、沙子和水填满玻璃瓶？
类比方案解法：先放鸡蛋，再放……。方案数量无穷多，因为我可以只旋转杯子。
对应问题观点：方案数量肯定为偶数，因为我可以旋转数组！即方案中4放在位置1和位置3其实没有什么不同。可以对方案进行剪枝。
选择次数：2 * 2 + 2
结论：41312432、23421314
6、结论
共有两种放置方案。
感谢各位提供方案和观点的同学，感谢聪明的妹妹。
