全排列问题

一  给定一个字符串求该字符串的第k个子串。

1 一个长度为len的字符串，它的总的子串的个数为1+2+3...+len = len*(len+1)/2;
2 利用优先队列的方法：最开始先用char数组存入1个字符，因为刚开始肯定是1个字符，然后出队再将出队的那个字符串最后一个字符的下一个字符合并后再压入队列中，出队k-1次后第k次出队的就是第k大的。
比如abc，先进a,b,c，然后a先出，接着ab进，就这样反复模拟...
3 优先队列应该重载“<”，那么这样就可以使得队列里面是按照字典序排好。

代码：

例如输出字符串str，求字符串的第k个子串。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

#define MAXN 100010

int t , k;
char str[MAXN];

struct Node{
   char s[MAXN];
   int pos;
   int index;
   friend bool operator<(Node a , Node b){
      if(strcmp(a.s , b.s) > 0)
        return true;
      return false;
   }
};
priority_queue<Node>q;

int main(){
    scanf("%d" , &t);
    while(t--){
       scanf("%s%d" , str , &k);
       int len = strlen(str);

       if(k*2 > len*(len+1)){
          printf("No such line.\n\n");
          continue;
       }
       while(!q.empty())
           q.pop();
       for(int i = 0 ; i < len ; i++){
           Node node;
           node.pos = 0;
           node.index = i;
           memset(node.s , '\0' , sizeof(node.s));
           node.s[node.pos++] = str[i];
           q.push(node);
       } 

       for(int i = 0 ; i < k-1 ; i++){
          Node tmp = q.top();
          q.pop();
          if(tmp.index != len-1){
            tmp.s[tmp.pos++] = str[++tmp.index];
            q.push(tmp);
          }
       }
       printf("%s\n\n" , q.top().s);
    }
    return 0;
}

二  给定字符串求以该字符串为第一个排列，求第k个全排列的字符串
利用STL的next_perputation()函数，假设经过k次的循环后没有那么说明不存在输出-1，否则输出这第k个全排列字符串

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define N 20

int main(){
   char str[N];
   int k;
   scanf("%s" , str);
   scanf("%d" , &k);
   int len = strlen(str);
   int cnt = 1;
   sort(str , str+len);
   while(next_permutation(str , str+len)){
      if(cnt == k){
        printf("%s\n" , str);
        break;
      }
      cnt++;
   }
   if(cnt != k)
     printf("-1\n");
   return 0;
}

三  给定n个数求这n个数的第k个全排列

首先先对n个数进行排序，然后利用next_perputation()函数即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define N 20

int main(){
   int num[N];
   int n , k;
   scanf("%d%d" , &n , &k);
   for(int i = 0 ; i < n ; i++)
      scanf("%d" , &num[i]);
   sort(num , num+n);
   int cnt = 1;
   while(next_permutation(num , num+n)){
      if(cnt == k){
        printf("%d" , num[0]);
        for(int i = 1 ; i < n ; i++)
           printf(" %d" , num[i]);
        break;
      }
      cnt++;
   }
   if(cnt != k)/*没有输出-1*/
     printf("-1\n");
   return 0;
}