黑马程序员技术交流社区

标题: 求高效算法。1-n的全排列。 [打印本页]
作者: 寇龙飞    时间: 2012-9-14 15:53
标题: 求高效算法。1-n的全排列。
给定整数n(0<n<10),求1-n的全排列,例如给定3,全排列为123、132、213、231、312、321。

要效率最高的实现方式。

为了看效果，打印出n为10000时1-n的全排列，看下需要运算的时间。
作者: 马睿    时间: 2012-9-14 17:18
本帖最后由 马睿 于 2012-9-14 17:35 编辑

我只能给你算法，但是不能帮你做题
关于全排列比较有名的是Johnson-Trotter算法：

对于一组顺序的数字1 2 3 ...n
上面都给他们一个向←的箭头
←    ←    ←         ←
1     2      3 ........n
步骤1:寻找最大的可移动元素k（这里是k=n）（也就是箭头方向旁边那个比他小的，比如3←，而3的左边是2，则3是可移动元素，当然这里最大可移动的是n）

步骤2：将n不断的向左移动（移动一小 格输出1次），直到尽头
步骤3：然后反向所有比“当前元素k” （目前k=n）  大的元素箭头标记
←    ←             ←    ←   
1     2     .....    n     n-1   （移动1小格）
....
....（步骤略= =！）
....
←   ←    ←             ←
n     1     2     .....    n-1（移动到了尽头，没比k=n更加小的了）

显然第一次没有比k大的，然后n移到尽头了，是个不可移动元素了是吧？所以要重新寻找最大移动元素k，

重复步骤1：显然这里是新k=n-1




重复步骤2：开始移动n-1

←    ←             ←    ←   
n     1     .....    n-1      n-2   （移动1小格）
....
....（步骤略= =！）
....
←   ←    ←             ←
n     n-1     1    .....    n-2（移动到了尽头，没比k=n-1更加小的了） 而n比n-1大，所以到靠近n就不能移动了


重复步骤3：反向比k=n-1大的元素

→   ←    ←             ←
n     n-1     1    .....    n-2

嘿嘿嘿！发现了么？n被反向了，它又可以动了，是的，再反回去

重复步骤1：找到最大可移动元素k=n

重复步骤2：移动k=n

←    ←             ←    →
n-1     1    .....    n-2   n     (n再次到达尽头！无法移动，再次执行步骤3，以此类推)

附送构建程序思路：
1创建一个数据储存类
class Num
{
     /*用来存放数据*/
     public int num;
     /*用来表达箭头*/
     public boolean arrowFlag;
}

class FullArray
{
    public static void main(String[] args)
    {
          Num nums[] = new Num[10000];
          for ( int i = 1; i <= 10000; i++ )
          {
                nums.num = i;
                /*false代表向左，ture代表向右*/
                nums.arrowFlag = flase;
          }
    }
   
     public void Fullsort()
     {
            /*your enforce code here (^w^) */
     }
}



完









作者: 舒远    时间: 2012-9-14 17:27
  1. /**
  2.   * 字符数组全排列
  3.   *
  4.   * @param a
  5.   * @param start
  6.   * @param set
  7.   */
  8. static void perm(char a[], int start, HashSet<String> set) {
  9.   if (start == a.length - 1) {
  10.    // 输出排列结果
  11.    set.add(new String(a));
  12.    return;
  13.   }
  14.   else {
  15.    for (int i = start; i <= a.length - 1; i++) {
  16.     // 将数组片段的各元素与首元素交换
  17.     swapArrayElements(a, start, i);
  18.     // 对交换后的，去掉首元素的数组片段进行全排列
  19.     perm(a, start + 1, set);
  20.     // 交换回来
  21.     swapArrayElements(a, start, i);
  22.    }
  23.   }
  24. }
  25. }
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2