快速业务通道

浅析实现排列组合查询算法 - 编程入门网

作者 佚名技术 来源 NET编程 浏览 发布时间 2012-06-17

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

时间:2011-05-25

所谓的排列组合查询就相当于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] = 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 +

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务,公司网站:http://www.lingzhong.cn 为了给广大客户了解更多的技术信息,本技术文章收集来源于网络,凌众科技尊重文章作者的版权,如果有涉及你的版权有必要删除你的文章,请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息,谢谢!

分享到: 更多

Copyright ©1999-2011 厦门凌众科技有限公司 厦门优通互联科技开发有限公司 All rights reserved

地址(ADD):厦门软件园二期望海路63号701E(东南融通旁) 邮编(ZIP):361008

电话:0592-5908028 传真:0592-5908039 咨询信箱:web@lingzhong.cn 咨询OICQ:173723134

《中华人民共和国增值电信业务经营许可证》闽B2-20100024  ICP备案:闽ICP备05037997号