J2SE综合－－浅析实现排列组合查询算法

goodluck · 发表于 2010-2-20 13:48:00

所谓的排列组合查询就相当于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个单词的所有排列情况，比如：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" }; 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 得到了他门所有的排列组合: %1%2%3% %1%3%2% %2%1%3% %2%3%1% %3%1%2% %3%2%1% 由此,我们可以很轻易的得到给定关键字的排列组合了. 需要注意的是,如果查询是输入关键字过多,比如5个则会有120中的组合,6个是720种,要是10个以上的话......所以该算法不适合很多关键字的全排列查询. 当然我的思路是最土和直接的,远不如GOOGLE,只是一种实现而已，如果文章对诸位有所帮助，便起到了作用。谁有更好的方法希望您也能共享出来。

账号		自动登录	找回密码
密码			论坛注册

J2SE综合－－浅析实现排列组合查询算法

浏览过的版块

客服中心

投诉建议