黑马程序员技术交流社区

标题: 求高效算法。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