杨大哥 这个我也能搞定 在北大的ACM上过了
不过是用C++写的 搞了个类  最近在学C++
不过发现自己的程序怎么好绕啊（成绩是 Memory 248k time 454MS 不理想啊）
贴出来 看能不能优化下 （不好意思 在C坛贴C++ 只是想和杨大哥交流算法，重点是配合杨大哥的调查）

#include <iostream>
using namespace std;
int g_array[1024];

///////////////////////////
// construct the class
///////////////////////////
class permutation
{
public:
    void set_array(int);
    void change();
    int len;
    int array[1024];
};

void permutation::set_array(int i_n)
{
    int i;
    len = i_n;
    for (i = 0; i < len; i++)
        array[i] = g_array[i];
}

void permutation::change()
{
    int i, flag = 0, j, k, temp, lager, min;

       for (i = len - 1; i >= 1; i--)
    {
        if (array[i] - array[i-1] == -1)
            continue;
        else break;   
    }
    if (i == 0)
        flag = 1;
    else
        flag = 0;

    if (flag)
    {
        for (i = 0; i < len; i++)
            array[i] = i + 1;
    }
    else
    {
       
        for (i = len - 1; i >= 1; i--)
        {
            if (array[i] < array[i-1])
                continue;
            else break;
        }
        i--;

        for (j = i + 1; j < len; j++)
        {       
            if (array[j] > array[i])
                  lager = j;
            break;
        } 
        for ( k = j + 1; k < len; k++)
            if (array[k] > array[i] && array[k] < array[lager])
                lager = k;

            temp = array[lager];
                array[lager] = array[i];
                array[i] = temp;

        for (j = i + 1; j < len - 1; j++)
        {
            min = j;
            for (k = j + 1; k < len; k++)
            {
                if (array[min] > array[k])
                    min = k;               
            }
            if (min != j)
            {
                int temp;
                temp = array[min];
                array[min] = array[j];
                array[j] = temp;
            }
        }
    }
}
////////////////////////////
// main entry point
////////////////////////////
int main(void)
{
    int m, n, k, i;

    permutation per;
   
    cin >> m ;
    while (m--)
    {
        scanf("%d%d", &n, &k);
        for (i = 0; i < n; i++)
            scanf("%d", &g_array[i]);
        per.set_array(n);
        for (i = 0; i < k; i++)
             per.change();
        for (i = 0; i < n; i++)
            printf("%d ", per.array[i]);
        printf("\n");
    }
   
    return 0;
}

[ 本帖最后由 有容就大 于 2012-5-30 20:03 编辑 ]

收到的鲜花

• beyondyf 于 2012-05-30 20:17 送鲜花  45朵   附言：我很赞同

是有点绕。代码看起来像小说，有过多的逻辑修饰。比如这段

       for (i = len - 1; i >= 1; i--)
     {
         if (array[i] - array[i-1] == -1)
             continue;
         else break;  
     }

  
用一句 for(i = len - 1; i >= 1 && array[i] - array[i - 1] == -1; i--);
就完全实现了你的逻辑。看起来也清爽明了。其它部分也是如此，flag则完全没必要。

呵呵，多加练习吧。

本来等着楼主回复，不过看起来这哥们消失了。那我的代码就送给大家参详吧。
北大这题很搞。我自信满满地把代码送给老杨，结果老杨告诉我TLE。我不信，亲自试，果然。百思不得其解，O(n)的算法怎么能超时呢？再试，无果。无意间换了提交语言，由GCC换成了C。结果就AC了。无语。

#include<stdio.h>

void next_permutation(int * s, int len)
{
    int i, j, k, t;
    for(i = len - 1; i && s[i] < s[i - 1]; i--);
    for(j = i, k = len - 1; j < k; j++, k--){ t = s[j]; s[j] = s[k]; s[k] = t;}
    if(!i) return;
    for(j = i--; s[i] > s[j]; j++);
    t = s[i]; s[i] = s[j]; s[j] = t;
}

int main()
{
    int s[2048], m, n, k, i;
    for(scanf("%d", &m); m--;)
    {
        scanf("%d%d", &n, &k);
        for(i = 0; i < n; scanf("%d", &s[i++]));
        while(k--) next_permutation(s, n);
        printf("%d", s[0]);
        for(i = 1; i < n; printf(" %d", s[i++]));
        puts("");
    }
    return 0;
}

 

哈哈 是啊 我都是一板一眼的写代码 不会融合的哪

还有 flag = 1 标志 排列是全部逆序的情况 n, n-1, n-2,...,2, 1.
当时写的时候我也不想用标志的 但是要得出这个标志需要一段不少的代码 就只好分出去了。

不知道有什么简洁的方法让全逆序放在if()的括号里又看起来顺当。

望尘莫及啊 好好看看先。

排列组合的题应该是比较常规了。不过自己仔细研究研究的话也能学到不少的东西。
gcc 的源码，是标准算法。大家有兴趣的也可以研究一下。
first 和 last 可以看成是一个指针，指向一个数组的首尾。它用于变换这个数组，以得到其字典序的下一个组合。
返回值是它是否变换成功。如果数组长度为0，或者已经是组合的最大值。比如 321，则会返回 false。

  template<typename _BidirectionalIterator>
    bool
    next_permutation(_BidirectionalIterator __first,
             _BidirectionalIterator __last)
    {
      // concept requirements
      __glibcxx_function_requires(_BidirectionalIteratorConcept<
                  _BidirectionalIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<
        typename iterator_traits<_BidirectionalIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);

      if (__first == __last)
    return false;
      _BidirectionalIterator __i = __first;
      ++__i;
      if (__i == __last)
    return false;
      __i = __last;
      --__i;

      for(;;)
    {
      _BidirectionalIterator __ii = __i;
      --__i;
      if (*__i < *__ii)
        {
          _BidirectionalIterator __j = __last;
          while (!(*__i < *--__j))
        {}
          std::iter_swap(__i, __j);
          std::reverse(__ii, __last);
          return true;
        }
      if (__i == __first)
        {
          std::reverse(__first, __last);
          return false;
        }
    }
    }

最开始的那几句是是 c++ 标准库的要求，大家可以无视。
for 前的那几个 if 是用于判断数组的长度是否是 1 或者 0。是的话，直接返回 false。否则 i 指向最后一个元素。(在 c++ 里，last 是最后一个元素的后一个位置。)

重要的部分是 for 里的内容。
第一步，它要在队尾找一个递减的子列。这是  if (*__i < *__ii) 这个语句做的。ii 如影随形地跟着 i 往前退，当这个判断成立时，ii 指向递减子列的第一个元素。
  在这个过程中，如果 i 到达了 first。就说明整个序列已经是逆序的了。这是字典序的最大排列。把它逆向，得到的是最小排列。同时 reture false，表示不能找到下一个排列了。
第二步，在那个子列里找一个比 i 稍大的元素。因为子列是递减的。只用从后往前找第一个比 i 大的即可。用 j 指向这个元素。
第三步，对调 i 和 j 指向的元素。之后倒转 ii 和 last 之间的元素。

这个算法我觉得是显然的，只要自己找几个序列观察一下，很快就会发现这些规律。
之所以展示这个代码，是因为这个代码写的很漂亮。注意到，这里有不能使用 i+1 这样语句的限制。

下面看一个例子：1 3 6 5 4 2 （感谢 有容就大 提供这个例子，这个例子以上三个步骤都用到了，比我原来的那个更清楚）


哦。另外再顺带提一句，这个源码的有几个语句看上去有点笨拙，主要是它应用的条件仅是双向顺序表。也就是支持 ++p 和 --p 操作的顺序表就可以。
所以不能用 first+1 == last 之类的语句，只能用 i = first; ++i == last 这么判断。同理也不能用 i = last-1; 只能用 i = last; --i。
熟悉 c++ 的人可能知道，一般来说 ++i 不一定等于 i+1。不熟悉的也不要紧。不要迷惑于此就好了。

另外在提点几句，为什么这里要用 swap 和 reverse 这两个通用算法(这在 c++ 里很常见。)。是出于效率和正常性的考虑。
在 c++ 里，指针 i 指向的对象很可能不是简单的 int 或者 char。
比如是一个 string。那么 string t = a; a = b; b = t 这样的写法，会引发大量的内存拷贝。但 swap(a, b) 不用，因为这个函数会使用内置的方法(以函数重载方式实现)，将这两个 string 内部指向动态申请内存的指针交换一下。这样 swap 两个 string 的开销和 swap 两个指针一致。另外，单纯 a = b 这么写可能还会引发深浅拷贝的问题。swap 的写法，给程序员留了重载这个函数的机会。如果不考虑这些通用性，其实这个算法和 beyondyf 的那个就是一样的。

我讲解这些正好给大家一个认识 c 和 c++ 区别的机会。经常有人说 c++ 和 c 应该看成两种不同语言，主要就是因为它们思考问题的方式太不相同。不仅体现在 c++ 是个面向对象这一点上。
最开始的那个语句我没解释。现在也补上吧，完整点。它们是为了在编译时验证：
 i 是不是能做前置的 ++ 和 -- 这个两个运算(虽然这个算法不要求可以做 i+1 这种运算，但是要求可以 ++i)。
i 指向的对象是否可以施用 < 这种比较方式，做为一个很常见的例子，两个复数是不能比大小的。
和 first last 所指向的空间是否合法(最起码，first 这个指针不能在 last 后面)。


[ 本帖最后由 pangding 于 2012-6-1 13:04 编辑 ]

收到的鲜花

• beyondyf 于 2012-05-31 07:31 送鲜花  45朵  

太牛了，我就是搞不定这种问题

会不会是你的函数和 STL 的库函数重名呢？你换一个名字试试呢？

跟函数名没关系，我又没引用任何STL库

都不太积极。点个名吧。

草狼、hellovfp、Devil_W

还有其他觉得自己可以解的，来领分！！！！！！！！（不需要实际解决，觉得自己可以，有思路就行）

一方面是调查一下，之后打算和各位合作玩个游戏。

[ 本帖最后由 beyondyf 于 2012-5-31 12:16 编辑 ]