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

goodluck 发表于 2010-2-20 14:18:52

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

所谓的排列组合查询就相当于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; 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 < a int j = a.length - 2; while (a > a) { j--; } // Find index k such that a is smallest integer // greater than a to the right of a int k = a.length - 1; while (a > a) { k--; } // Interchange a and a temp = a; a = a; a = 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; a = 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]).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,只是一种实现而已，如果文章对诸位有所帮助，便起到了作用。谁有更好的方法希望您也能共享出来。

页: [1]

鸿鹄论坛's Archiver

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