排列组合的实现

实现排列组合查询算法

作者：    文章来源：

发布日期：2005年01月01日    浏览次数：1次 所谓的排列组合查询就相当于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,只是一种实现而已，如果文章对诸位有所帮助，便起到了作用。谁有更好的方法希望您也能共享出来。

Jegg

java-j2se-algorithm

共享就是力量！        

  public void inductionExcelData(String companyid, String fileid, String fileRealPath)

  {

    try

    {

      UploadDAO uploadDAO = new UploadDAO();

      Workbook book = Workbook.getWorkbook(new File(fileRealPath + "/upload/file/" + uploadDAO.getFileName(fileid)));

      Sheet sheet = book.getSheet(0);

      int rowNum = sheet.getRows();

      Cell cell = null;

      String[] objtext = new String[5];

      RecordSet rscompanyusered = this.userDAO.getRecordSetByCompanyId(companyid);

      for (int i = 1; i < rowNum; i++) {

        for (int j = 0; j < 5; j++) {

          cell = sheet.getCell(j, i);

          objtext[j] = cell.getContents().trim();

        }

        if (objtext[2].indexOf("男") >= 0)

          objtext[2] = "1";

        else {

          objtext[2] = "2";

        }

        objtext[3] = StringUtils.getStringDate2String9(objtext[3]);

        if (!StringUtils.dataisright(objtext[0]))

        {

          continue;

        }

        if (validatorMobile(objtext[0], rscompanyusered))

          this.userDAO.insertCompanyUser(objtext[0], objtext[1], companyid, objtext[2], objtext[3], objtext[4]);

      }

    }

    catch (Exception e) {

      e.printStackTrace();

    }

  }