 |
|
|
|
|
所谓的排列组合查询就相当于GOOGLE高级查询中“包含以下全部的字词”查询，也就是说查询中必须包含所有查询关键词，而且他们的顺序可以是任意。以下程序段实现了这一功能。比如输入查询关键字:tom tina则最一般的情况是在程序中使用类似于"select sex from student where name like '%tom%tina%' or name like '%tina%tom%' ordered by age" 的查询语句实现以上的查询,因此如何得到'%tina%tom%' 和'%tom%tina%' 就是该程序和算法要实现的. //------------------------------------ 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,只是一种实现而已，如果文章对诸位有所帮助，便起到了作用。谁有更好的方法希望您也能共享出来。
|
相关文章 推荐文章
