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

浅析实现排列组合查询算法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 + 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（））;
}
}
}