1 2 下一页

　　所谓的排列组合查询就相当于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 得到了他门所有的排列组合:

(责任编辑：admin)