按字典顺序生成所有的排列

　　因为最近在做Project Euler上的题，里面涉及到的都是和数学有关问题，有一些数学概念会反复出现。比如判断一个数是否为素数，求一些元素的全排列之类。为了方便起见，我把一些功能写成函数，以便以后重复使用。这个帖子介绍的是将一些元素所有的全排列按字典顺序依次生成的函数。

☆ Scala代码

/**
   &#Util.scala
   utils for mathematical algorithm,include:
   # generate all permutations in lexicographical order
   
   @author Eastsun
*/
package eastsun.math

object Util {
    /**
      Rearranges the elements in the Array[T] src into the lexicographically next smaller permutation of elements.
      The comparisons of individual elements are performed using operators <= and >= in Ordered[T]
      @return true if the function rearranged the array as a lexicographicaly smaller permutation.
    */
    def prevPermutation[T](src:Array[T])
                    (implicit view:(T) => Ordered[T]):Boolean = {
        var i = src.length - 2
        while(i >= 0 && src(i) <= src(i+1)) i -= 1
        if(i < 0) return false
        var j = src.length - 1
        while(src(j) >= src(i)) j -= 1
        adjustArray(src,i,j) 
        true
    }
    
    /**
      Rearranges the elements in the Array[T] src into the lexicographically next greater permutation of elements.
      The comparisons of individual elements are performed using operators <= and >= Ordered[T]
      @return true if the function rearrange the array as a lexicographicaly greater permutation.
    */
    def nextPermutation[T](src:Array[T])
                    (implicit view:(T) => Ordered[T]):Boolean = {
        var i = src.length - 2
        while(i >= 0 && src(i) >= src(i+1)) i -= 1
        if(i < 0) return false
        var j = src.length - 1
        while(src(j) <= src(i)) j -= 1
        adjustArray(src,i,j)
        true
    }
    
    private def adjustArray[T](src:Array[T],i:Int,j:Int){
        var tmp = src(i)
        src(i) = src(j)
        src(j) = tmp
        var len = (src.length - i)/2
        for(k <- 1 to len){
            tmp = src(src.length - k)
            src(src.length - k) = src(i + k)
            src(i + k) = tmp
        }
    }
}

　　算法没什么特别的，如果不清楚google一下即可，这儿就简单说明一下代码。Util中含两个public方法：

def prevPermutation[T](src:Array[T])(implicit view:(T) => Ordered[T]):Boolean
def nextPermutation[T](src:Array[T])(implicit view:(T) => Ordered[T]):Boolean

　　顾名思义，第一个prevPermutation方法是将数组src重排成比当前字典顺序小的上一个排列。注意该方法的返回值为Boolean：如果存在比当前字典顺序小的排列，则重排src，并返回true；否则不影响src并返回false。还算有两点需要注意的地方：
　　1.该方法第二个参数view是implicit的，所以调用该方法的时候可以省略。只需要保证类型T有一个到Ordered[T]类型的隐式转换就可以了。
　　2.该方法第一个参数src中允许有重复的元素。
　　　比如对于1,2,3,3,其所有排列按字典顺序排列为：
　　　　1233
　　　　1323
　　　　1332
　　　　2133
　　　　2313
　　　　2331
　　　　3123
　　　　3132
　　　　3213
　　　　3231
　　　　3312
　　　　3321

☆ 应用
　　下面就通过解决Project Euler中的两个题来示范一下如何使用这两个API。

题目24：What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
题目简介：将数字0, 1, 2, 3, 4, 5, 6, 7, 8 ,9的所有排列按字典顺序排序，求排在第1,000,000位的那个数字。(注意：从第一位记起)
　　当然这个题有更高效的解决方法，可以参看Euler Project解题汇总 023 ~ 030。这里就使用nextPermutation方法暴力解决：

import eastsun.math.Util._

object Euler024 extends Application {
    var src = Array(0,1,2,3,4,5,6,7,8,9)
    for(idx <- 1 until 1000000) nextPermutation(src)
    println(src.mkString(""))
}

问题41：What is the largest n-digit pandigital prime that exists?
题目简介：一个数称为pandigital，如果它是数字1，2，……，n的一个排列。比如2143就是一个4位的pandigital。
　　现在求所有pandigital中最大的那个素数。
解题思路：我们先不对这个问题进行进一步数学上的分析，直接想怎么用蛮力法去解决它。显然，我们可以先从9位的pandigital从大大小进行尝试，如果找到了一个素数，那么这个数就是所求；否则，再对8位的pandigital从大到小进行尝试……如此直到找到一个素数为止，这个素数就是问题的答案。
　　下面就是依照这个思路写的代码：

import eastsun.math.Util._

object Euler041 extends Application {



    def isPrime(n:Int) = 2.to(math.sqrt(n).toInt).forall{ n%_ != 0}
    
    var buf = Array(9,8,7,6,5,4,3,2,1)
    var idx = 0
    var res = 0
    while(res == 0){
        var src = buf.slice(idx,buf.length)//subArray(idx,buf.length)
        do{
            var num = src.foldLeft(0){ _*10 + _ }
            if(isPrime(num)) res = num
        }while(res == 0&&prevPermutation(src))
        idx += 1
    }
    println(res)
}

　　虽然是很野蛮的方法，但这段代码已经够用了，只需要2秒左右就能得到答案。不过只要再简单思考一下，就可以瞬时找到答案。如果你高中数学还学得马马虎虎，应该不难验证：一个数能被3整除当且仅当这个数的各位数字之和能被3整除。这样就可以知道9位的pandigital里面不可能有素数，因为1+2+3+..+9 = 45能被三整除，同样可以知道8位的pandigital里面也没有素数。所以事实上我们从7位的pandigital试起就可以。

评论

1 楼 naff 2008-06-25  

嗯,不错,收藏了...