挑剔数列介绍:
挑剔数列问题是一个有趣的数学问题。
给定正整数n,对1~n的这些整数,每个数字取两个,进行全排列,使得任意两个相同数字a[i]之间间隔a[i]个数字。求满足条件的排列以及排列数。
eg1: n = 3 可以列举出如下两个满足条件的排列:
2 3 1 2 1 3
3 1 2 1 3 2 他们其实互为逆序排列,本质上是一个组合方式。
eg2: n = 4
2 3 4 2 1 3 1 4
4 1 3 1 2 4 3 2
total:2
当n变大的时候,排列数变得很多,问题变得复杂化,怎么解决呢?
在排列问题中,我们采用递归的方式求所有的排列方式。
这个问题相当于带条件的排列问题。
排列问题中我们采用深度优先搜索(dfs)的方法,搜索可行解。
我们有两种做法:
1.求出2n个数的全排列,然后判断排列是否符合条件。
2.直接构造、搜索满足的排列。
相比之下,第一种复杂度比第二种高的多。
本文采用递归/深度优先搜索的方法,实现第二种方法。
数据结构及其定义:
integer: n,len(n的位数),sum 总的方案数,use,使用数字个数,m返回栈顶元素
array: p[2n] 用来存储排列结果
used[2n] 用来标记是否对应位置是否使用
stack: s 用来保存排列位置的信息
stack也可以用vector来实现。
算法:
dfs深度优先搜索 : permute(pos) 考虑索引为pos的位置填充方法。
结果展示:
n=7
7 1 4 1 5 6 7 4 2 3 5 2 6 3 7 1 4 1 6 7 3 4 5 2 3 6 2 7 5 1 5 1 4 6 7 3 5 4 2 3 6 2 7 1 5 1 6 3 7 4 5 3 2 6 4 2 7 1 5 1 6 7 2 4 5 2 3 6 4 7 3 1 5 1 7 3 4 6 5 3 2 4 7 2 6 1 6 1 3 5 7 4 3 6 2 5 4 2 7 1 6 1 7 2 4 5 2 6 3 4 7 5 3 1 7 1 2 5 6 2 3 4 7 5 3 6 4 1 7 1 2 6 4 2 5 3 7 4 6 3 5 2 3 6 2 7 3 4 5 1 6 1 4 7 5 2 3 7 2 6 3 5 1 4 1 7 6 5 4 2 4 7 2 3 6 4 5 3 1 7 1 6 5 2 5 6 2 3 7 4 5 3 6 1 4 1 7 2 6 3 2 5 7 3 4 6 1 5 1 4 7 2 6 3 2 7 4 3 5 6 1 4 1 7 5 2 6 7 2 1 5 1 4 6 3 7 5 4 3 2 7 4 2 3 5 6 4 3 7 1 5 1 6 3 4 5 7 3 6 4 1 5 1 2 7 6 2 3 4 6 7 3 2 4 5 2 6 1 7 1 5 3 5 7 2 3 6 2 5 4 1 7 1 6 4 3 5 7 4 3 6 2 5 4 2 7 1 6 1 3 6 7 1 3 1 4 5 6 2 7 4 2 5 3 7 4 6 3 2 5 4 2 7 6 1 5 1 4 1 6 1 7 4 3 5 2 6 3 2 7 5 4 1 7 1 6 4 2 5 3 2 7 6 3 5 4 5 6 7 1 4 1 5 3 6 2 7 3 2 4 6 1 7 1 4 3 5 6 2 3 7 2 5 4 6 1 7 1 4 5 2 6 3 2 7 5 3 4 6 3 5 7 4 3 2 6 5 2 1 7 1 5 1 7 1 6 2 5 4 2 3 7 6 4 3 5 2 4 6 2 7 5 4 3 1 6 1 3 7 5 2 4 7 2 6 5 4 1 3 1 7 6 3 5 2 6 4 2 7 5 3 4 6 1 3 1 7 5 2 7 3 2 6 5 3 4 1 7 1 6 4 5 3 6 4 7 3 5 2 4 6 2 1 7 1 5 3 6 7 2 3 5 2 4 6 1 7 1 4 5 6 1 7 1 3 5 4 6 3 2 7 4 2 5 7 1 4 1 6 5 3 4 7 2 3 6 2 5 7 2 3 6 2 5 3 4 7 1 6 1 4 5 7 2 6 3 2 5 4 3 7 6 1 4 1 5 7 4 1 6 1 5 4 3 7 2 6 3 2 6 1 5 1 7 3 4 6 5 3 2 4 7 2 6 2 7 4 2 3 5 6 4 3 7 1 5 1 7 1 3 1 6 4 3 5 7 2 4 6 2 5 7 1 4 1 6 3 5 4 7 3 2 6 5 2 7 2 4 5 2 6 3 4 7 5 3 1 6 1 7 2 4 6 2 3 5 4 7 3 6 1 5 1 7 2 6 3 2 4 5 3 7 6 4 1 5 1 7 3 1 6 1 3 4 5 7 2 6 4 2 5 7 3 6 2 5 3 2 4 7 6 5 1 4 1 7 4 1 5 1 6 4 3 7 5 2 3 6 2 total:52
n=8
8 1 3 1 6 7 3 8 5 2 4 6 2 7 5 4 8 1 3 1 6 8 3 4 7 5 2 6 4 2 8 5 7 1 3 1 6 8 3 5 7 2 4 6 2 5 8 4 7 1 3 1 6 8 3 7 4 2 5 6 2 4 8 7 5 1 3 1 7 5 3 8 6 4 2 5 7 2 4 6 8 1 3 1 7 8 3 5 2 6 4 2 7 5 8 4 6 1 3 1 8 5 3 6 7 2 4 5 2 8 6 4 7 1 3 1 8 6 3 7 2 4 5 2 6 8 4 7 5 1 4 1 5 6 8 4 7 3 5 2 6 3 2 8 7 1 4 1 5 7 8 4 3 6 5 2 3 7 2 8 6 1 4 1 5 8 6 4 7 2 5 3 2 6 8 3 7 1 4 1 8 6 3 4 7 5 3 2 6 8 2 5 7 1 5 1 4 6 7 8 5 4 2 3 6 2 7 3 8 1 5 1 6 4 7 8 5 3 4 6 2 3 7 2 8 1 5 1 6 7 3 8 5 4 3 6 2 7 4 2 8 1 5 1 6 7 8 2 5 4 2 6 3 7 4 8 3 1 5 1 7 3 6 8 5 3 4 2 7 6 2 4 8 1 5 1 7 3 8 6 5 3 2 4 7 2 6 8 4 1 5 1 8 4 7 3 5 6 4 3 2 8 7 2 6 1 5 1 8 6 2 7 5 2 3 4 6 8 3 7 4 1 6 1 3 7 5 8 3 6 4 2 5 7 2 4 8 1 6 1 3 7 8 4 3 6 5 2 4 7 2 8 5 1 6 1 3 8 5 7 3 6 2 4 5 2 8 7 4 1 6 1 5 8 4 7 3 6 5 4 3 2 8 7 2 1 6 1 7 2 8 5 2 6 3 4 7 5 3 8 4 1 6 1 7 4 8 3 5 6 4 3 7 2 5 8 2 1 6 1 8 2 5 7 2 6 3 4 5 8 3 7 4 1 6 1 8 2 7 4 2 6 5 3 4 8 7 3 5 1 7 1 2 6 8 2 5 3 7 4 6 3 5 8 4 1 7 1 2 8 5 2 4 6 7 3 5 4 8 3 6 1 7 1 2 8 5 2 6 3 7 4 5 3 8 6 4 1 7 1 2 8 6 2 3 5 7 4 3 6 8 5 4 1 7 1 3 5 6 8 3 4 7 5 2 6 4 2 8 1 7 1 3 8 4 5 3 6 7 4 2 5 8 2 6 1 7 1 4 5 8 6 3 4 7 5 3 2 6 8 2 1 7 1 4 6 8 3 5 4 7 3 6 2 5 8 2 1 7 1 4 8 5 3 6 4 7 3 5 2 8 6 2 1 7 1 6 2 8 5 2 4 7 6 3 5 4 8 3 1 7 1 6 3 8 4 5 3 7 6 4 2 5 8 2 1 7 1 8 2 4 6 2 5 7 4 3 8 6 5 3 1 8 1 3 4 7 5 3 6 4 8 2 5 7 2 6 1 8 1 4 6 3 7 5 4 3 8 6 2 5 7 2 1 8 1 5 2 6 7 2 4 5 8 3 6 4 7 3 1 8 1 5 3 7 4 6 3 5 8 4 2 7 6 2 2 3 6 2 8 3 4 7 5 6 1 4 1 8 5 7 2 3 8 2 4 3 6 7 5 4 1 8 1 6 5 7 2 3 8 2 4 3 7 5 6 4 1 8 1 5 7 6 2 3 8 2 7 3 6 1 5 1 4 8 7 6 5 4 2 4 5 2 6 8 4 7 5 3 1 6 1 3 8 7 2 4 5 2 8 6 4 7 5 1 3 1 6 8 3 7 2 4 6 2 5 8 4 7 3 6 5 1 3 1 8 7 2 4 6 2 7 8 4 5 1 6 1 3 7 5 8 3 2 4 7 2 8 6 4 1 5 1 7 3 6 8 5 3 2 4 8 2 3 7 4 6 3 5 1 8 1 7 6 5 2 5 7 2 3 6 8 5 3 4 7 1 6 1 4 8 2 5 7 2 6 3 8 5 4 3 7 6 1 4 1 8 2 5 7 2 8 3 4 5 6 3 7 4 1 8 1 6 2 5 7 2 8 6 1 5 1 4 7 3 6 8 4 3 2 5 8 2 4 7 3 5 6 4 3 8 1 7 1 6 2 6 3 2 7 8 3 5 6 1 4 1 7 5 8 4 2 6 3 2 8 5 3 7 6 4 1 5 1 8 4 7 2 6 4 2 7 8 3 4 6 5 3 1 7 1 8 5 2 6 7 2 4 8 5 3 6 4 7 3 5 1 8 1 2 6 7 2 8 1 5 1 6 4 7 3 5 8 4 3 2 6 8 2 1 7 1 4 6 5 3 8 4 7 3 5 2 6 8 2 5 3 7 4 6 3 5 8 4 1 7 1 2 7 3 2 5 8 3 4 6 7 5 1 4 1 8 6 2 7 4 2 8 5 3 4 6 7 3 5 1 8 1 6 2 7 5 2 6 8 3 4 5 7 3 6 4 1 8 1 2 7 8 2 3 4 5 6 3 7 4 8 5 1 6 1 2 8 1 2 1 5 6 7 3 4 8 5 3 6 4 7 2 8 1 2 1 5 7 4 6 3 8 5 4 3 7 6 2 8 1 2 1 6 4 7 5 3 8 4 6 3 5 7 2 8 1 2 1 6 7 3 4 5 8 3 6 4 7 5 2 8 1 2 1 7 4 6 3 5 8 4 3 7 6 5 2 8 1 2 1 7 5 3 6 4 8 3 5 7 4 6 2 8 3 2 4 6 3 7 5 4 8 1 6 1 5 7 2 8 4 2 3 6 7 4 3 5 8 1 6 1 7 5 2 8 5 2 4 6 7 3 5 4 8 3 6 1 7 1 2 8 5 2 6 3 7 4 5 3 8 6 4 1 7 1 2 8 5 2 7 1 6 1 5 4 8 3 7 6 4 3 2 8 5 2 7 3 4 6 5 3 8 4 7 1 6 1 2 8 6 2 1 7 1 4 5 6 8 3 4 7 5 3 2 8 6 2 3 5 7 4 3 6 8 5 4 1 7 1 3 1 7 1 3 5 8 6 4 2 7 5 2 4 6 8 3 1 7 1 3 6 8 5 2 4 7 2 6 5 4 8 3 1 7 1 3 8 4 5 6 2 7 4 2 5 8 6 3 1 7 1 3 8 6 4 2 5 7 2 4 6 8 5 3 1 8 1 3 4 6 7 5 2 4 8 2 6 5 7 3 1 8 1 3 4 7 5 6 2 4 8 2 5 7 6 3 1 8 1 3 6 7 2 4 5 2 8 6 4 7 5 3 1 8 1 3 7 5 2 6 4 2 8 5 7 4 6 3 4 5 6 3 8 4 7 5 2 6 1 2 1 8 7 3 4 6 7 3 8 4 5 1 6 1 7 2 5 8 2 3 4 7 8 3 2 4 6 2 5 7 1 8 1 6 5 3 4 8 5 3 7 4 2 6 5 2 8 1 7 1 6 3 4 8 5 3 7 4 6 1 5 1 8 2 7 6 2 3 4 8 6 3 7 4 1 5 1 6 8 2 7 5 2 3 5 6 4 3 7 8 5 4 6 1 2 1 7 2 8 3 5 6 8 3 2 7 5 2 6 4 1 8 1 7 4 3 5 6 8 3 4 7 5 2 6 4 2 8 1 7 1 3 5 6 8 3 7 1 5 1 6 4 2 8 7 2 4 3 5 7 4 3 8 6 5 4 1 7 1 2 6 8 2 3 5 8 2 3 7 2 5 6 4 1 8 1 7 4 6 3 5 8 6 3 7 1 5 1 4 6 8 2 7 4 2 3 6 2 7 3 2 8 5 6 4 1 7 1 5 4 8 3 6 2 8 3 2 7 5 6 1 4 1 8 5 7 4 3 6 4 5 3 7 8 4 6 5 1 2 1 7 2 8 3 6 7 2 3 8 2 4 6 5 7 1 4 1 8 5 3 6 8 1 3 1 5 7 6 4 2 8 5 2 4 7 3 6 8 1 3 1 7 4 6 5 2 8 4 2 7 5 3 6 8 1 3 1 7 5 6 2 4 8 2 5 7 4 3 7 2 6 3 2 8 4 5 7 6 1 4 1 5 8 3 7 4 6 3 8 5 4 2 7 6 2 5 1 8 1 3 7 5 8 3 1 6 1 5 7 4 2 8 6 2 4 3 7 8 2 3 4 2 5 6 7 4 8 1 5 1 6 3 8 2 5 3 2 7 4 6 5 8 1 4 1 7 6 3 8 4 5 3 6 7 4 2 5 8 2 6 1 7 1 3 8 4 7 3 2 6 4 2 5 8 7 1 6 1 5 3 8 4 7 3 6 2 4 5 2 8 7 6 1 5 1 3 8 5 2 3 6 2 7 5 4 8 1 6 1 4 7 3 8 5 7 3 1 6 1 5 4 8 7 2 6 4 2 3 8 6 1 3 1 5 7 4 6 8 2 5 4 2 7 3 8 6 2 3 5 2 7 4 6 8 5 1 4 1 7 4 1 6 1 7 4 8 3 5 6 2 3 7 2 5 8 4 1 6 1 7 4 8 5 2 6 3 2 7 5 3 8 4 1 6 1 8 4 5 7 2 6 3 2 5 8 3 7 4 1 8 1 7 4 2 5 6 2 3 8 7 5 3 6 4 2 5 7 2 4 8 6 5 3 1 7 1 3 6 8 4 2 5 8 2 4 6 7 5 1 3 1 8 6 3 7 4 2 6 8 2 4 3 7 5 6 3 1 8 1 5 7 4 2 6 8 2 4 7 5 1 6 1 3 8 5 7 3 4 2 7 5 2 4 8 6 3 5 7 1 3 1 6 8 4 2 7 8 2 4 6 1 5 1 7 3 8 6 5 3 4 5 6 7 3 4 8 5 3 6 2 7 1 2 1 8 4 5 6 7 8 4 1 5 1 6 3 7 2 8 3 2 4 5 7 8 1 4 1 5 6 3 7 2 8 3 2 6 4 5 8 6 3 4 7 5 3 2 6 8 2 1 7 1 4 6 1 7 1 4 8 5 6 2 3 7 2 5 3 8 4 6 1 8 1 4 7 3 6 5 2 3 8 2 7 5 4 6 3 5 8 4 3 7 6 5 1 2 1 8 2 7 4 6 3 7 8 4 3 2 6 5 2 7 1 8 1 5 4 6 7 2 8 4 2 3 6 5 7 3 1 8 1 5 4 6 8 2 5 4 2 7 6 3 5 8 1 3 1 7 4 6 8 3 5 4 7 3 6 2 5 8 2 1 7 1 4 7 1 6 1 4 8 5 3 7 6 2 3 5 2 8 4 7 1 8 1 4 3 5 6 7 3 2 8 5 2 6 4 7 1 8 1 4 6 2 5 7 2 3 8 6 5 3 4 7 3 8 5 4 3 6 2 7 5 2 8 1 6 1 4 7 3 8 6 4 3 2 5 7 2 6 8 1 5 1 4 7 5 2 8 4 2 6 5 7 1 3 1 8 6 3 4 7 5 3 6 4 8 3 5 7 2 6 1 2 1 8 4 7 5 8 1 4 1 6 5 7 2 3 8 2 6 3 4 7 8 2 5 4 2 6 3 7 5 8 3 1 6 1 4 8 1 5 1 4 6 7 3 5 8 2 3 6 2 7 4 8 3 5 7 4 3 6 2 5 8 2 7 1 6 1 4 8 5 2 6 4 2 7 5 3 8 6 1 3 1 7 4 8 5 3 6 4 7 3 5 2 8 6 2 1 7 1 4 8 5 7 1 4 1 6 5 3 8 7 2 3 6 2 4 8 6 2 7 4 2 3 5 6 8 3 7 1 5 1 5 1 6 1 7 8 5 2 4 6 2 3 7 4 8 3 5 1 6 1 8 4 5 7 3 6 4 2 3 8 2 7 5 1 7 1 8 3 5 4 6 3 7 2 4 8 2 6 5 1 8 1 3 6 5 7 3 4 2 8 6 2 4 7 5 1 8 1 3 7 5 6 3 2 4 8 2 7 6 4 5 1 8 1 7 2 5 6 2 3 4 8 7 3 6 4 5 2 4 7 2 8 5 4 6 3 1 7 1 3 8 6 5 2 4 8 2 7 5 4 6 1 3 1 8 7 3 6 5 2 8 3 2 7 5 3 6 4 1 8 1 7 4 6 5 2 8 6 2 3 5 7 4 3 6 8 1 4 1 7 5 3 6 4 8 3 5 7 4 6 1 2 1 8 2 7 5 3 7 4 8 3 5 6 4 1 7 1 2 8 6 2 5 3 7 8 2 3 5 2 6 4 7 1 8 1 4 6 5 3 7 8 4 3 5 6 2 4 7 2 8 1 6 1 5 6 1 8 1 4 5 7 6 3 4 2 8 3 2 7 5 6 1 8 1 7 5 2 6 4 2 3 8 7 4 3 5 6 2 8 4 2 5 7 6 4 3 1 8 1 3 7 5 6 7 1 8 1 5 3 6 4 7 3 2 8 4 2 5 6 7 3 4 8 5 3 6 4 7 1 2 1 8 2 5 7 1 6 1 8 5 3 4 7 6 3 2 4 8 2 5 7 2 4 8 2 5 6 4 7 1 3 1 8 6 3 5 7 2 8 3 2 5 6 3 7 4 1 8 1 6 4 5 7 4 6 3 8 5 4 3 7 6 1 2 1 8 2 5 7 4 6 8 2 5 4 2 7 6 3 1 8 1 3 5 7 4 8 6 2 5 4 2 7 3 6 8 1 3 1 5 7 8 4 2 6 5 2 4 7 3 8 6 1 3 1 5 8 1 4 1 6 5 7 4 3 8 2 6 3 2 7 5 8 1 4 1 7 5 6 4 2 8 3 2 7 6 3 5 8 1 7 1 3 5 6 4 3 8 7 2 4 6 2 5 8 2 3 7 2 5 3 6 4 8 1 7 1 4 6 5 8 2 4 6 2 5 7 4 3 8 6 1 3 1 7 5 8 2 7 4 2 5 6 3 4 8 7 3 1 6 1 5 8 4 1 7 1 5 4 6 3 8 2 7 3 2 6 5 8 6 4 2 7 5 2 4 6 8 3 1 7 1 3 6 1 5 1 7 4 8 6 5 3 4 2 7 3 2 8 6 1 5 1 8 4 7 6 5 2 4 3 2 8 7 3 6 1 7 1 8 2 5 6 2 4 7 3 5 8 4 3 6 1 7 1 8 3 4 6 5 3 7 4 2 8 5 2 6 1 8 1 4 7 3 6 5 4 3 8 2 7 5 2 6 1 8 1 5 3 7 6 4 3 5 8 2 4 7 2 6 2 3 7 2 8 3 6 4 5 1 7 1 4 8 5 6 2 3 8 2 7 3 6 5 1 4 1 8 7 5 4 6 2 5 7 2 4 8 6 5 3 4 7 1 3 1 8 6 2 5 8 2 3 7 6 5 3 4 1 8 1 7 4 6 2 7 4 2 5 8 6 4 3 7 5 1 3 1 8 6 2 7 5 2 8 4 6 3 5 7 4 3 1 8 1 6 2 7 8 2 3 4 6 5 3 7 4 8 1 5 1 6 2 8 4 2 7 3 6 4 5 3 8 1 7 1 5 6 2 8 5 2 4 7 6 3 5 4 8 3 1 7 1 6 3 5 7 4 3 8 6 5 4 2 7 1 2 1 8 6 3 5 7 8 3 2 6 5 2 4 7 1 8 1 4 6 3 7 8 1 3 1 6 4 5 7 2 8 4 2 5 6 3 8 4 5 3 7 6 4 2 5 8 2 1 7 1 6 4 1 7 1 8 4 6 3 5 2 7 3 2 8 5 6 4 1 8 1 7 4 6 2 5 3 2 8 7 3 5 6 4 7 1 8 1 4 6 3 5 7 2 3 8 2 5 6 4 7 1 8 1 4 6 5 2 7 3 2 8 5 3 6 4 7 5 3 8 4 6 3 5 7 1 2 1 8 2 6 4 7 5 8 2 4 6 2 5 7 3 1 8 1 3 6 4 8 5 7 2 4 6 2 5 3 8 7 1 3 1 6 7 1 4 1 8 5 6 4 7 2 3 5 2 8 3 6 7 3 4 5 8 3 6 4 7 5 1 2 1 8 2 6 7 5 1 8 1 4 6 5 7 3 4 2 8 3 2 6 7 5 2 8 4 2 6 5 7 4 3 1 8 1 3 6 8 1 4 1 5 7 6 4 3 8 5 2 3 7 2 6 8 2 7 3 2 5 6 3 4 8 7 5 1 4 1 6 8 3 1 7 1 3 6 4 5 8 2 7 4 2 5 6 8 5 2 4 7 2 6 5 4 8 3 1 7 1 3 7 1 3 1 6 8 3 4 7 5 2 6 4 2 8 5 7 1 3 1 6 8 3 5 7 2 4 6 2 5 8 4 7 1 3 1 8 5 3 6 7 2 4 5 2 8 6 4 7 1 4 1 5 6 8 4 7 3 5 2 6 3 2 8 7 1 4 1 5 8 6 4 7 2 5 3 2 6 8 3 7 1 4 1 8 6 3 4 7 5 3 2 6 8 2 5 7 2 3 6 2 8 3 4 7 5 6 1 4 1 8 5 7 2 3 8 2 4 3 6 7 5 4 1 8 1 6 5 7 2 4 5 2 6 8 4 7 5 3 1 6 1 3 8 7 2 4 5 2 8 6 4 7 5 1 3 1 6 8 3 7 2 4 6 2 5 8 4 7 3 6 5 1 3 1 8 7 2 6 3 2 8 5 3 7 6 4 1 5 1 8 4 7 2 8 1 2 1 5 6 7 3 4 8 5 3 6 4 7 2 8 1 2 1 6 4 7 5 3 8 4 6 3 5 7 2 8 3 2 4 6 3 7 5 4 8 1 6 1 5 7 3 1 8 1 3 4 6 7 5 2 4 8 2 6 5 7 3 4 5 6 3 8 4 7 5 2 6 1 2 1 8 7 3 6 8 1 3 1 5 7 6 4 2 8 5 2 4 7 3 8 5 2 3 6 2 7 5 4 8 1 6 1 4 7 3 8 6 1 3 1 5 7 4 6 8 2 5 4 2 7 3 8 6 2 3 5 2 7 4 6 8 5 1 4 1 7 4 1 6 1 8 4 5 7 2 6 3 2 5 8 3 7 4 2 5 8 2 4 6 7 5 1 3 1 8 6 3 7 4 2 6 8 2 4 3 7 5 6 3 1 8 1 5 7 4 6 3 5 8 4 3 7 6 5 1 2 1 8 2 7 4 6 8 2 5 4 2 7 6 3 5 8 1 3 1 7 4 8 1 5 1 4 6 7 3 5 8 2 3 6 2 7 4 8 5 2 6 4 2 7 5 3 8 6 1 3 1 7 5 1 6 1 8 4 5 7 3 6 4 2 3 8 2 7 5 1 8 1 3 6 5 7 3 4 2 8 6 2 4 7 5 2 8 6 2 3 5 7 4 3 6 8 1 4 1 7 5 3 6 4 8 3 5 7 4 6 1 2 1 8 2 7 5 6 1 8 1 4 5 7 6 3 4 2 8 3 2 7 5 6 2 8 4 2 5 7 6 4 3 1 8 1 3 7 5 8 1 4 1 6 5 7 4 3 8 2 6 3 2 7 5 8 2 4 6 2 5 7 4 3 8 6 1 3 1 7 8 1 2 1 6 2 5 7 4 8 3 6 5 4 3 7 8 1 3 1 5 6 3 7 4 8 5 2 6 4 2 7 8 2 3 6 2 5 3 7 4 8 6 5 1 4 1 7 8 3 1 6 1 3 5 7 4 8 6 2 5 4 2 8 1 2 1 6 2 5 7 4 8 3 6 5 4 3 7 8 1 2 1 6 2 7 5 3 8 4 6 3 5 7 4 8 1 2 1 7 2 4 5 6 8 3 4 7 5 3 6 8 1 2 1 7 2 6 3 5 8 4 3 7 6 5 4 8 1 3 1 5 6 3 7 4 8 5 2 6 4 2 7 8 1 3 1 5 7 3 4 6 8 5 2 4 7 2 6 8 1 3 1 7 4 3 5 6 8 4 2 7 5 2 6 8 1 4 1 6 7 3 4 5 8 3 6 2 7 5 2 8 2 3 6 2 5 3 7 4 8 6 5 1 4 1 7 8 2 3 7 2 4 3 5 6 8 4 7 1 5 1 6 8 2 4 6 2 5 7 4 3 8 6 5 3 1 7 1 8 2 4 7 2 6 3 4 5 8 3 7 6 1 5 1 8 2 5 3 2 6 7 3 5 8 4 1 6 1 7 4 8 2 7 1 2 1 5 6 4 8 7 3 5 4 6 3 8 2 7 1 2 1 6 4 5 8 7 3 4 6 5 3 8 2 7 3 2 6 4 3 5 8 7 4 6 1 5 1 8 3 1 6 1 3 5 7 4 8 6 2 5 4 2 7 8 3 5 2 7 3 2 6 5 8 4 1 7 1 6 4 8 3 5 7 2 3 6 2 5 8 4 7 1 6 1 4 8 3 7 2 6 3 2 4 5 8 7 6 4 1 5 1 8 4 1 6 1 7 4 3 5 8 6 3 2 7 5 2 8 4 2 6 7 2 4 3 5 8 6 3 7 1 5 1 8 4 2 7 5 2 4 6 3 8 5 7 3 1 6 1 8 4 5 1 7 1 4 6 5 8 2 3 7 2 6 3 8 4 5 6 2 7 4 2 5 8 6 3 1 7 1 3 8 4 5 7 2 6 4 2 5 8 3 7 6 1 3 1 8 5 1 4 1 6 7 5 4 8 2 3 6 2 7 3 8 5 2 7 3 2 6 5 3 8 4 7 1 6 1 4 8 6 1 3 1 7 5 3 6 8 4 2 5 7 2 4 8 6 3 1 7 1 3 5 6 8 4 2 7 5 2 4 8 6 4 2 5 7 2 4 6 8 5 3 1 7 1 3 8 6 4 2 7 5 2 4 6 8 3 5 7 1 3 1 total:300
n再大复杂度就相当高了,数据比较庞大,这里就不列举了。
Code
1 #include<cstdio> 2 #include<stack> 3 #include<vector> 4 #include<iostream> 5 #include<algorithm> 6 #include<cstring> 7 #include<iomanip> 8 using namespace std; 9 10 int n,len,sum=0,p[200],used[200],m,use=0; 11 //vector<int> vec; 12 stack<int> s; 13 void init(){ 14 memset(p,0,sizeof(p)) ; 15 memset(used,0,sizeof(used)); 16 use=0; 17 //vec.clear(); 18 } 19 20 void permute(int pos){ 21 int i; 22 if(use>=n){ //use记录本次排列中已用过多少个数 23 sum++;//排列结果加1 24 for(int i=0;i<2*n-1;i++) //输出结果 25 cout<<setw(len)<<p[i]<<" "; 26 cout<<setw(len)<<p[2*n-1]<<endl; 27 //init(); //只输出一种。。 28 return ; 29 } 30 if(p[pos]==0){ //如果该位置上0 尝试可能的数 31 for(i=0;i<n;i++){ 32 if(!used[i]){ //如果i+1没有被使用过则考虑 33 //pos+i+1+1位置上是否为0 34 // 如果是0则i+1放到该位置 35 if((pos+i+2)<(n*2)){ 36 if(p[pos+i+2]==0){ 37 p[pos]=i+1; 38 p[pos+i+2]=i+1; 39 //vec.push_back(pos); 40 s.push(pos); 41 //if(!s.push(pos)) return;//本次放数位置放入栈 42 used[i]=1; 43 use++; 44 permute(pos+1);//排下一位置 45 if(s.empty()) return; 46 else{ 47 //m = vec.back();vec.pop_back(); 48 m = s.top();s.pop(); 49 //回溯,从栈中取出最后一次入栈的位置到m 50 used[p[m]-1]=0; 51 p[m+p[m]+1]=0; 52 p[m]=0; 53 use--; 54 } 55 }else 56 continue; 57 }else 58 return; 59 }else 60 continue; 61 } 62 }else 63 permute(pos+1); //如果第pos位有数,则考察第pos+1位 64 } 65 int Digit(int x){ 66 int cnt=0; 67 while(x){ 68 cnt++; 69 x/=10; 70 } 71 return cnt; 72 } 73 74 int main(){ 75 cin>>n; 76 len = Digit(n); 77 init(); 78 permute(0); 79 cout<<"total:"<<sum<<endl; 80 return 0; 81 }
文末附上参考链接
关于是否有可行排列的问题,请参考: https://wenku.baidu.com/view/8dcd06bc960590c69ec376e7.html
参考文献:
[1].孙陆鹏,吕廷勤.挑剔程序的C程序实现及优化[N].太原城市职业技术学院学报.2007(7):152-153.