"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将那些常量悬挂起来最后组合一下就可以了.以下程序给出了排列组合输出的实现:
</td> </tr> <tr> <td width="63%" height="20">
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 + 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[s];
a[s] = 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[i]]).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个以上的话......所以该算法不适合很多关键字的全排列查询.
</td> </tr> </table>
↑返回目录
前一篇: Sun认证Java程序员5.0升级版本
后一篇: 漫谈Java语言的接口与类型安全