Go语言视频零基础入门到精通

javalearner

所谓的排列组合查询就相当于Google高级查询中“包含以下全部的字词”查询，也就是说查询中必须包含所有查询关键词，而且他们的顺序可以是任意。以下程序段实现了这一功能。比如输入查询关键字:tom tina,则最一般的情况是在程序中使用类似于

"select sex from student where name like "%tom%tina%" or name like "%tina%tom%" ordered by age"

的查询语句实现以上的查询,因此如何得到"%tina%tom%" 和"%tom%tina%" 就是该程序和算法要实现的.

首先想到的就是写出一个排列组合的算法，然后用该算法输出所要查询关键字的所有情况，比如输入了以下几个关键字:
       EGG APPLE TIME
则要写一个程序输出这3个单词的所有排列情况，比如：
情况1 EGG APPLE TIME ,
情况2 EGG TIME APPLE，
情况3 APPLE EGG TIME......
不用说，大家一看就知道应该是3的阶乘种情况也就是1*2*3这里就不一一列出了。

写出一段程序,或者一个函数比如：
  public String paileizuhe(String inputstr){......}

该函数返回一个排列组合好的QUERY字符串,比如使用该函数并赋予他两个字符串参数(tom,tina)则:
public String pailiezuhe("tom","tina")输出:
"select sex from student where name like "%tom%tina%" or name like "%tina%tom%" ordered by age "  

这里,我们关心的是如何生成tom tina 的组合即"%tina%tom%" 和"%tom%tina%" 至于生成整个如上的字符串是非常简单的只要用StringBuffer将那些常量悬挂起来最后组合一下就可以了.以下程序给出了排列组合输出的实现:


   
  
  
   import java.math.BigInteger;
import java.util.*;

public class PermutationGenerator {

     private int[] a;
     private BigInteger numLeft;
     private BigInteger total;
     public PermutationGenerator(int n) {
         if (n < 1) {
             throw new IllegalArgumentException("Min 1");
         }
         a = new int[n];
         total = getFactorial(n);
         reset();
     }

     //------
     // Reset
     //------

     public void reset() {
         for (int i = 0; i < a.length; i++) {
             a = i;
         }
         numLeft = new BigInteger(total.toString());
     }

     //------------------------------------------------
     // Return number of permutations not yet generated
     //------------------------------------------------

     public BigInteger getNumLeft() {
         return numLeft;
     }

     //------------------------------------
     // Return total number of permutations
     //------------------------------------

     public BigInteger getTotal() {
         return total;
     }

     //-----------------------------
     // Are there more permutations?
     //-----------------------------

     public boolean hasMore() {
         return numLeft.compareTo(BigInteger.ZERO) == 1;
     }

     //------------------
     // Compute factorial
     //------------------

     private static BigInteger getFactorial(int n) {
         BigInteger fact = BigInteger.ONE;
         for (int i = n; i > 1; i--) {
             fact = fact.multiply(new BigInteger(Integer.toString(i)));
         }
         return fact;
     }

     //--------------------------------------------------------
     // Generate next permutation (algorithm from Rosen p. 284)
     //--------------------------------------------------------

     public int[] getNext() {

         if (numLeft.equals(total)) {
             numLeft = numLeft.subtract(BigInteger.ONE);
             return a;
         }

         int temp;

         // Find largest index j with a[j] < a[j+1]

         int j = a.length - 2;
         while (a[j] > a[j + 1]) {
             j--;
         }

         // Find index k such that a[k] is smallest integer
         // greater than a[j] to the right of a[j]

         int k = a.length - 1;
         while (a[j] > a[k]) {
             k--;
         }

         // Interchange a[j] and a[k]

         temp = a[k];
         a[k] = a[j];
         a[j] = temp;

         // Put tail end of permutation after jth position in increasing order

         int r = a.length - 1;
         int s = j + 1;

         while (r > s) {
             temp = a;
             a = a[r];
             a[r] = temp;
             r--;
             s++;
         }

         numLeft = numLeft.subtract(BigInteger.ONE);
         return a;

     }
//程序测试入口
     public static void main(String[] args) {

         int[] indices;
         String[] elements = { "1", "2", "3" ,"4"};
         PermutationGenerator x = new PermutationGenerator(elements.length);
         StringBuffer permutation;

         while (x.hasMore()) {
             permutation = new StringBuffer("%");
             indices = x.getNext();
             for (int i = 0; i < indices.length; i++) {
                 permutation.append(elements[indices]).append("%");
             }
             System.out.println(permutation.toString());

         }
     }

}

可以看到我们输入1 2 3 得到了他门所有的排列组合:
C:java>java PermutationGenerator
%1%2%3%4%
%1%2%4%3%
%1%3%2%4%
%1%3%4%2%
%1%4%2%3%
%1%4%3%2%
%2%1%3%4%
%2%1%4%3%
%2%3%1%4%
%2%3%4%1%
%2%4%1%3%
%2%4%3%1%
%3%1%2%4%
%3%1%4%2%
%3%2%1%4%
%3%2%4%1%
%3%4%1%2%
%3%4%2%1%
%4%1%2%3%
%4%1%3%2%
%4%2%1%3%
%4%2%3%1%
%4%3%1%2%
%4%3%2%1% C:java>
由此,我们可以很轻易的得到给定关键字的排列组合了.
需要注意的是,如果查询是输入关键字过多,比如5个则会有120中的组合,6个是720种,要是10个以上的话......所以该算法不适合很多关键字的全排列查询.

  
  
   
   

   
     
   

     
   
  



  
  
   
   

     
   

     
   
  
  

源码下载：http://file.javaxxz.com/2014/10/29/235934500.zip