最新公告
  • 欢迎您光临波比源码,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 常见算法之全排列 全组合

    全排列算法是1种比较常考的算法,他的做法也比较多样。

    首先我们来看看最符合我们直观思考的,思路是这样的:假设没有重复元素时,传入1个数组A,并插入到另外1个数组B中,假设B中已包括这个元素,则跳过,否则插入数组B。我们来看看具体代码:

    <span style="font-size:14px;">public static void permutation1(final String str, String buffer){
    if (str.length() == buffer.length()){
    System.out.println((num++) + ":" + buffer);
    return;
    }

    for (int i = 0; i < str.length(); i++){
    if (buffer.indexOf((int)str.charAt(i)) < 0){
    permutation1(str, buffer + str.charAt(i));
    }
    }
    }</span>


    这个看代码就比较容易理解,所以就不多说了,它有缺点,就是不能有重复,那我们改1改,给每个值都安置1个状态位,假设插入过置为1,没有则是0,所以,我们又有了第2种方法:

    <span style="font-size:14px;">public static void permutation2(final char[][] array, String result, int len){

    if (result.length() == len){
    System.out.println(result);
    }else{
    for (int i = 0; i < len; i++){
    if (array[i][1] == 0){
    array[i][1] = 1;
    permutation2(array, result + array[i][0], len);
    array[i][1] = 0;
    }
    }
    }
    }</span>

    固然它也有缺点,我们需要在这之前对他传入数组进行转化。例如

    <span style="font-size:14px;">public static void main(String[] args) {
    String str = "abcd";
    char[][] array = new char[str.length()][2];
    for (int i = 0; i < str.length(); i++){
    array[i][0] = str.charAt(i);
    array[i][1] = 0;
    }
    String result = new String();
    permutation2(array, result, str.length());
    }</span>


    现在还有另外1种递归方法,假设我们的数组是abc 那末全排列的话有abc,acb,bac,bca,cba,cab。

    也就是说,a开头的和{b,c}的全排列,b开头的和{a,c}的全排列,c开头的和{a,b}全排列。

    p = {r1,r2,r3,r4…} , 设 pn = p – {rn}

    perm(p) = r1perm(p1) + r2perm(p2) + r3perm(p3) + ….

    可以看出每个全排列可以继续分成更多的子全排列,而每一个子排列可使看成第1个字母与别的字母调换位置得来的。所以,我们还可以用以下代码求结果:

    <span style="font-size:14px;">public static void swap(char[] array, int from, int to){
    char temp = array[from];
    array[from] = array[to];
    array[to] = temp;
    }

    public static void permutation3(char[] array, int n){
    if (n == array.length){
    System.out.println(new String(array));
    }else {
    for (int i = n; i < array.length; i++){
    swap(array, i, n);
    permutation3(array, n + 1);
    swap(array, i, n);
    }
    }
    }</span>


    但是呢,我们介绍的全部都是递归的算法,想要非递归怎样办呢。

    首先我们来看这样1个字符串1234,需要他的全排列,怎样求呢,1243,1342依此类推就能够得出全部了,但是,这依此类推是怎样类推法。首先,我们规定需要将传入的字符串进行排序,小的在前大的在后。然后我们需要从前想后找前面的数小于后面的数的点,我们先叫他替换点,例如:938740,从后往前找,3是1个替换点。找到替换点以后,我们继续从后往前找,找到第1个大于他的数,照旧是上面这个例子:937840,那这个数就是4了。好了,现在将他们进行替换,现在这个数变成947830了。然后我们需要把它从替换点这,进行反转,把7840转为0478,并与之前的数进行合并930478。然后从重复这个动作,就可以找到全部的数了。


    <span style="font-size:14px;">public static void reversal(char array[], int from, int to){
    while (from < to){
    swap(array, from++, to–);
    }
    }

    public static boolean hasNext(char[] array){
    if (array.length == 0 || array == null){
    return false;
    }

    int endIndex = array.length – 1;
    int q = endIndex – 1;
    int p = endIndex;
    while (q >= 0){
    if (array[q] < array[q + 1]){
    while (array[q] > array[p]){
    p–;
    }
    swap(array, p, q);
    reversal(array, q + 1, array.length – 1);
    return true;
    }
    q–;
    }
    reversal(array, 0, array.length – 1);
    return false;

    }

    public static void main(String[] args) {
    char[] array = "abc".toCharArray();
    do {
    System.out.println(array);
    } while (hasNext(array));
    }</span>


    但是,但是,但是,假设有是有重复字符的字符串,那要怎样办呢。还有假设某些字符是需要依照某种顺序呢,我表示我还在想,假设你知道的话,欢迎知道留言邮件都行:630841816@qq.com




    以上是全排列,下面我们来讲全组合

    首先我们来看个例子,p={a,b,c}的全组合:asse(p) = {},{a},{b},{c},{ab}…..

    到这我们似乎可以看到1些规律:

    {} => 000
    {a} => 001 {b} => 010  

    我们可以把他们和对逐一对应,如此,我们1个值在0~size(asse(p))的值就一定代表1个唯1的值。

    所以我们可以:

    <span style="font-size:14px;">public static void assembly(char[] array){
    int num; //全组合的组数
    num = 1 << array.length;
    for (int i = 0; i < num; i++){
    StringBuffer buffer = new StringBuffer();
    for (int j = 0; j < array.length; j++){
    if ((i & (1 << j)) > 0){
    buffer.append(array[j]);
    }
    }
    System.out.println(buffer);
    }
    }</span>

    波比源码 – 精品源码模版分享 | www.bobi11.com
    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
    3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

    波比源码 » 常见算法之全排列 全组合

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    波比源码
    一个高级程序员模板开发平台
    升级波友尊享更多特权立即升级