康拓展开

http://baike.baidu.com/item/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80?force=1

就是百度百科的康拓展开解决魔板问题的代码打了一遍调试了一下长了一下姿势

感觉就是和状压一样展开就是为了标记？

一共只有8格即8!=40320个状态

用ans记录下每个状态从12345678开始最快能变到的步骤

init就是一次从12345678开始搜到底的bfs ( 所谓搜到底就是遍历了每一个状态

但是输入的起点(即初始状态)不是12345678怎么办呢？

比如输入的是82754631 17245368

我们只需要把这串数与12345678一一对应

也就是把8看成1，2看成2，7看成3，5看成4，4看成5，6看成6，3看成7，1看成8

那么我们希望得到的最终状态就相当于83254761

于是我们只要求出83254761的康诺展开它对应的ans就是答案。

 1 //由于此题数字1~8，康托展开的所有情况为8!，共40320种
 2 LL JC[]={1,1,2,6,24,120,720,5040};//康托展开中用到的0~7的阶乘
 3 string ans[50005];
 4 struct node
 5 {
 6     int a[8];
 7     int n;
 8 }front, rear;
 9 queue<node> q;
10 bool vis[50005];
11 void A(node &t) // 上下两行互换
12 {
13     swap(t.a[0], t.a[7]);
14     swap(t.a[1], t.a[6]);
15     swap(t.a[2], t.a[5]);
16     swap(t.a[3], t.a[4]);
17 }
18 void B(node &t)  // 每行同时循环右移一格
19 {
20     swap(t.a[3], t.a[2]);
21     swap(t.a[2], t.a[1]);
22     swap(t.a[1], t.a[0]);
23     swap(t.a[4], t.a[5]);
24     swap(t.a[5], t.a[6]);
25     swap(t.a[6], t.a[7]);
26 
27 }
28 void C(node &t) // 中间4个方块顺时针旋转一格
29 {
30     swap(t.a[1], t.a[6]);
31     swap(t.a[6], t.a[5]);
32     swap(t.a[5], t.a[2]);
33 }
34 int contor(node &t)
35 {
36     int num=0;
37     for(int i=0;i<8;i++)
38     {
39         int tmp=0;
40         for(int j=i+1;j<8;j++)
41             if(t.a[j]<t.a[i])
42                 tmp++;
43         num+=tmp*JC[7-i];
44     }
45     return num;
46 }
47 void init()
48 {
49     memset(vis, 0, sizeof(vis));
50     while(!q.empty())
51         q.pop();
52     vis[0]=1;
53     for(int i=0;i<8;i++) //由初始状态12345678开始
54         front.a[i]=i+1;
55     front.n=contor(front);
56     q.push(front);
57     void (*way[3])(node&);       //定义函数指针
58     way[0]=A, way[1]=B, way[2]=C;//指向对应函数方便处理
59     while(!q.empty())
60     {
61         front=q.front();
62         q.pop();
63         for(int i=0;i<3;i++) //三种变换
64         {
65             rear=front;
66             (way[i])(rear);
67             rear.n=contor(rear); //对副本执行操作并康托展开
68             if(!vis[rear.n])    //重复
69             {
70                 char ch='A'+i;
71                 ans[rear.n]=ans[front.n]+ch;   //当前排列的步数
72                 vis[rear.n]=1;
73                 q.push(rear);
74             }
75         }
76     }
77 }
78 char a[10], b[10];
79 int n[10];
80 int main()
81 {
82     init();
83     while(~scanf("%s%s", a, b))
84     {
85         for(int i=0;i<8;i++)
86             n[a[i]-'0']=i+1;
87         for(int i=0;i<8;i++)
88             front.a[i]=n[b[i]-'0'];
89         cout<<ans[contor(front)]<<endl;
90     }
91     return 0;
92 }
93 /*
94 12345678
95 17245368
96 
97 12345678
98 82754631
99 */

本来想这种方法写一次八数码，然后发现预处理12345678的方法行不通，因为8(也就是x)所在的位置直接影响变换也就是不能把某个数字当成是8

然后直接从输入的状态开始搜的话先后经历了WA TLE MLE之后放弃了。。。

逆展开

计算k个数字的全排列(从小到大) 第x+1个排列是：

 1 int JC[]={1,1,2,6,24,120,720,5040,40320,362880};
 2 int ans[9];  // 返回的数组
 3 void uncantor(int x, int k)   //k个数字的全排列的 第x+1个
 4 {
 5     bool h[12];
 6     for(int i=1; i<=k; i++)
 7     {
 8         int t=x/JC[k-i];
 9         x-=t*JC[k-i];
10         int j, l=0;
11         for(j=1; l<=t; j++)
12             if(!h[j])
13                 l++;
14         j--;
15         h[j]=true;
16         ans[i-1]=j;
17     }
18 }
19 int main()
20 {
21     uncantor(95, 5);
22     for(int i=0;i<5;i++)
23         printf("%d", ans[i]);
24     return 0;
25 }

C代码

  1 import java.io.*;
  2 import java.util.*;
  3 import java.math.*;
  4 
  5 public class Main
  6 {
  7     static BigInteger li=BigInteger.ZERO;
  8     static BigInteger yi=BigInteger.ONE;
  9     static BigInteger er=BigInteger.valueOf(2);
 10     static BigInteger ten=BigInteger.valueOf(10);
 11     static BigInteger []JC=new BigInteger[25];
 12     static int []ans=new int[20];
 13     public static void getJC()
 14     {
 15         JC[0]=yi;
 16         for(int i=1;i<=20;i++)
 17             JC[i]=JC[i-1].multiply(BigInteger.valueOf(i));
 18     }
 19     public static void uncantor(BigInteger x, int k)
 20     {
 21         boolean []h=new boolean[25];
 22         for(int i=0;i<25;i++)
 23             h[i]=false;
 24         for(int i=1;i<=k;i++)
 25         {
 26             BigInteger t=x.divide(JC[k-i]);
 27             x=x.subtract(t.multiply(JC[k-i]));
 28             int j, l=0;
 29             int tt=t.intValue();
 30             for(j=1;l<=tt;j++)
 31                 if(!h[j])
 32                     l++;
 33             j--;
 34             h[j]=true;
 35             ans[i-1]=j;
 36         }
 37     }
 38     public static void main(String[] args)
 39     {
 40         InputReader in = new InputReader();
 41         PrintWriter out = new PrintWriter(System.out);
 42         getJC();
 43         while(in.hasNext())
 44         {
 45             BigInteger x=in.nextBigInteger();
 46             int k=in.nextInt();
 47             uncantor(x, k);
 48             for(int i=0;i<k;i++)
 49                 out.print(ans[i]);
 50         }
 51         out.close();
 52     }
 53 }
 54 class InputReader
 55 {
 56     BufferedReader buf;
 57     StringTokenizer tok;
 58     InputReader()
 59     {
 60         buf = new BufferedReader(new InputStreamReader(System.in));
 61     }
 62     boolean hasNext()
 63     {
 64         while(tok == null || !tok.hasMoreElements()) 
 65         {
 66             try
 67             {
 68                 tok = new StringTokenizer(buf.readLine());
 69             } 
 70             catch(Exception e) 
 71             {
 72                 return false;
 73             }
 74         }
 75         return true;
 76     }
 77     String next()
 78     {
 79         if(hasNext()) 
 80             return tok.nextToken();
 81         return null;
 82     }
 83     int nextInt()
 84     {
 85         return Integer.parseInt(next());
 86     }
 87     long nextLong()
 88     {
 89         return Long.parseLong(next());
 90     }
 91     double nextDouble()
 92     {
 93         return Double.parseDouble(next());
 94     }
 95     BigInteger nextBigInteger()
 96     {
 97         return new BigInteger(next());
 98     }
 99     BigDecimal nextBigDecimal()
100     {
101         return new BigDecimal(next());
102     }
103 }

大数java