所謂的排列組合查詢就相當於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 + 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" };
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 得到了他門所有的排列組合:
%1%2%3%
%1%3%2%
%2%1%3%
%2%3%1%
%3%1%2%
%3%2%1%
由此,我們可以很輕易的得到給定關鍵字的排列組合了.
需要注意的是,如果查詢是輸入關鍵字過多,比如5個則會有120中的組合,6個是720種,要是10個以上的話......所以該算法不適合很多關鍵字的全排列查詢.
當然我的思路是最土和直接的,遠不如GOOGLE,只是一種實現而已，如果文章對諸位有所幫助，便起到了作用。誰有更好的方法希望您也能共享出來。
