高效的java版排列组合算法

本文实例为大家分享了java排列组合算法的具体代码，供大家参考，具体内容如下

package BeanUtil;
import java.util.ArrayList;
import java.util.List;
import com.work.core.exception.OurException;
/**
 * 统计任三出现的最多的几率的组合
 *
 * @author wangmingjie
 * @date 2009-1-1下午01:22:19
 */
public class Copy_2_of_StatisAnyThree {
// 组合算法
//  本程序的思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标
//  代表的数被选中，为0则没选中。
//  首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。
//  然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为
//  “01”组合，同时将其左边的所有“1”全部移动到数组的最左端。
//  当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得
//  到了最后一个组合。
//  例如求5中选3的组合：
//  1  1  1  0  0  //1,2,3
//  1  1  0  1  0  //1,2,4
//  1  0  1  1  0  //1,3,4
//  0  1  1  1  0  //2,3,4
//  1  1  0  0  1  //1,2,5
//  1  0  1  0  1  //1,3,5
//  0  1  1  0  1  //2,3,5
//  1  0  0  1  1  //1,4,5
//  0  1  0  1  1  //2,4,5
//  0  0  1  1  1  //3,4,5
  public static void main(String[] args) {
    Copy_2_of_StatisAnyThree s = new Copy_2_of_StatisAnyThree();
    s.printAnyThree();
  }

  /**
   *
   */
  public void printAnyThree(){
    int[] num = new int[]{1,2,3,4,5,6};
    print(combine(num,3));
  }
  /**
   * 从n个数字中选择m个数字
   * @param a
   * @param m
   * @return
   */
  public List combine(int[] a,int m){
    int n = a.length;
    if(m>n){
      throw new OurException("错误！数组a中只有"+n+"个元素。"+m+"大于"+2+"!!!");
    }

    List result = new ArrayList();

    int[] bs = new int[n];
    for(int i=0;i<n;i++){
      bs[i]=0;
    }
    //初始化
    for(int i=0;i<m;i++){
      bs[i]=1;
    }
    boolean flag = true;
    boolean tempFlag = false;
    int pos = 0;
    int sum = 0;
    //首先找到第一个10组合，然后变成01，同时将左边所有的1移动到数组的最左边
    do{
      sum = 0;
      pos = 0;
      tempFlag = true;
      result.add(print(bs,a,m));

      for(int i=0;i<n-1;i++){
        if(bs[i]==1 && bs[i+1]==0 ){
          bs[i]=0;
          bs[i+1]=1;
          pos = i;
          break;
        }
      }
      //将左边的1全部移动到数组的最左边

      for(int i=0;i<pos;i++){
        if(bs[i]==1){
          sum++;
        }
      }
      for(int i=0;i<pos;i++){
        if(i<sum){
          bs[i]=1;
        }else{
          bs[i]=0;
        }
      }

      //检查是否所有的1都移动到了最右边
      for(int i= n-m;i<n;i++){
        if(bs[i]==0){
          tempFlag = false;
          break;
        }
      }
      if(tempFlag==false){
        flag = true;
      }else{
        flag = false;
      }

    }while(flag);
    result.add(print(bs,a,m));

    return result;
  }

  private int[] print(int[] bs,int[] a,int m){
    int[] result = new int[m];
    int pos= 0;
    for(int i=0;i<bs.length;i++){
      if(bs[i]==1){
        result[pos]=a[i];
        pos++;
      }
    }
    return result ;
  }

  private void print(List l){
    for(int i=0;i<l.size();i++){
      int[] a = (int[])l.get(i);
      for(int j=0;j<a.length;j++){
        System.out.print(a[j]+"/t");
      }
      System.out.println();
    }
  }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • java实现字符串排列组合问题

    本文为大家介绍了java实现字符串排列组合问题,供大家参考,具体内容如下 import java.util.ArrayList; import java.util.Collections; /** * 输入一个字符串,按字典序打印出该字符串中字符的所有排列.例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac, * bca,cab和cba. * * @author pomay * */ public class Solution_stringarrange

  • Java获得一个数组的指定长度排列组合算法示例

    本文实例讲述了Java获得一个数组的指定长度排列组合算法.分享给大家供大家参考,具体如下: package demo; import java.util.Stack; /** * JAVA获得一个数组的指定长度的排列组合.<br> * * @author JAVA世纪网(java2000.net, laozizhu.com) */ public class TestSequenceAll { public static void main(String[] args) { TestSequen

  • Java递归实现字符串全排列与全组合

    排列组合算法用途广泛,需要掌握,为降低门槛,本文主要关注算法的逻辑和简易性,未重视算法效率. 结合网络书本上的实现和自己的需求,这里列有四个目标: 1. 所有元素的全排列: ab的全排列是ab, ba(顺序相关); 2. 所有元素的全组合: ab的全组合是a, b, ab(顺序无关); 3. 求n个元素中选取m个元素的组合方式有哪些: abc中选2个元素的组合是ab, ac, bc; 4. 求n个元素中选取m个元素的排列方式有哪些: abc中选2个元素的排列是ab, ba, ac, ca, bc

  • java数组排列组合问题汇总

    面试或笔试中,多次遇到以下4个关于排列组合的手撕算法,这里做个笔记,方法日后查阅: 1. 无重复元素的数组,求全排列: 2. 有重复元素的数组,求全排列: 3. 无重复元素的数组,求组合[子集]: 4. 有重复元素的数组,求组合: 以上四类题,可以用统一的模板实现,如下所示: /* *[组合&&排列] *把一个数组里的数组合全部列出,比如1和2列出来为1,2,12,21. *这个题目可以扩展成四个: *1.无重复数字的数组,求组合 *2.有重复数字的数组,求组合 *3.无重复数字的数组,求

  • Java实现abc字符串排列组合

    Java实现abc字符串排列组合

    1.可重复排列:abc三个字符组成的所有长度为3的字符串,aaa,aab,aac......ccc 一共27种 利用递归的思想,第一个字符可以从abc中选择一个,三种选择,之后问题转化为abc组成长度为2的字符的情况,循环递归后可以求出所有的可能.控制好循环退出条件即可. 利用递归可以处理,不知道字符长度的情况下,即通用处理.如果知道长度,只需要利用多层循环,也可以得出结论. public class Permutation { public static void main(String[]

  • Java排列组合字符串的方法

    例如 输入"abc",打印所有可能出现的组合情况,并且消除重复值. 所谓排列组合如下: 排列组合,字符串:abc bca acb abc cba bac cab 排列组合个数:6 实现代码(结合Java8 lambda表达式实现) import org.junit.Test; import java.util.ArrayList; import java.util.HashSet; import java.util.List; public class test2 { @Test pu

  • Java实现多个数组间的排列组合

    Java多个数组之间的排列组合,具体内容如下 说明:有一批手机有各种颜色.各种尺寸.各种版本,然后要实现他们之间各种属性的组合. 定义各种属性 String[] color={"红色","白色","蓝色","金色"}; String[] size={"4.7寸","5.1寸","6.0寸"}; String[] version={"联通",&quo

  • 关于各种排列组合java算法实现方法

    一.利用二进制状态法求排列组合,此种方法比较容易懂,但是运行效率不高,小数据排列组合可以使用 复制代码 代码如下: import java.util.Arrays; //利用二进制算法进行全排列//count1:170187//count2:291656 public class test {    public static void main(String[] args) {        long start=System.currentTimeMillis();        count

  • 高效的java版排列组合算法

    本文实例为大家分享了java排列组合算法的具体代码,供大家参考,具体内容如下 package BeanUtil; import java.util.ArrayList; import java.util.List; import com.work.core.exception.OurException; /** * 统计任三出现的最多的几率的组合 * * @author wangmingjie * @date 2009-1-1下午01:22:19 */ public class Copy_2_o

  • 如何用Java实现排列组合算法

    需求 我们的数据表有多个维度,任意多个维度组合后进行 group by 可能会产生一些"奇妙"的反应,由于不确定怎么组合,就需要将所有的组合都列出来进行尝试. 抽象一下就是从一个集合中取出任意元素,形成唯一的组合.如[a,b,c]可组合为[a].[b].[c].[ab].[bc].[ac].[abc]. 要求如下: 组合内的元素数大于 0 小于等于 数组大小: 组合内不能有重复元素,如 [aab] 是不符合要求的组合: 组合内元素的位置随意,即 [ab] 和 [ba] 视为同一种组合:

  • 浅谈c语言中一种典型的排列组合算法

    浅谈c语言中一种典型的排列组合算法

    c语言中的全排列算法和组合数算法在实际问题中应用非常之广,但算法有许许多多,而我个人认为方法不必记太多,最好只记熟一种即可,一招鲜亦可吃遍天 全排列: #include<stdio.h> void swap(int *p1,int *p2) { int t=*p1; *p1=*p2; *p2=t; } void permutation(int a[],int index,int size) { if(index==size) { for(int i=0;i<size;i++) print

  • Golang排列组合算法问题之全排列实现方法

    本文实例讲述了Golang排列组合算法问题之全排列实现方法.分享给大家供大家参考,具体如下: [排列组合问题] 一共N辆火车(0<N<10),每辆火车以数字1-9编号,要求以字典序排序输出火车出站的序列号. 输入: 包括N个正整数(0<N<10),范围为1到9,数字之间用空格分割,字符串首位不包含空格. 输出: 输出以字典序排序的火车出站序列号,每个编号以空格隔开,每个输出序列换行. 样例输入: 1 2 3 样例输出: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3

  • C#实现排列组合算法完整实例

    排列组合是常见的数学问题,本文就以完整实例形式讲述了C#实现排列组合算法的方法.分享给大家供大家参考之用.具体方法如下: 首先,数学中排列组合,可表示为:排列P(N,R) 其实排列实现了,组合也就实现了,组合C(N,R)就是P(N,R)/P(R,R) ,实现这一功能比较简单的是递归算法,但考虑到递归的性能,下面采用了2种非递归的方法,具体代码如下 using System; using System.Collections.Generic; namespace Test { class Prog

  • PHP实现的简单排列组合算法应用示例

    本文实例讲述了PHP实现的简单排列组合算法应用.分享给大家供大家参考,具体如下: 一.问题: 给你一个40斤的西瓜,给3个人分,有多少种分法? 二.PHP实现代码: <?php $aa = range(1,40); $bb = array(); foreach($aa as $k=>$val){ foreach($aa as $v){ foreach($aa as $vl){ $sum = $val+$v+$vl; if($sum == 40){ $bb[$k][0] = $val; $bb[

  • JS实现的排列组合算法示例

    JS实现的排列组合算法示例

    本文实例讲述了JS实现的排列组合算法.分享给大家供大家参考,具体如下: 在数学中有排列组合,用来计算概率. 比如:从4个数字中,任意选择两个的情况.从5个数字中任意选择3个数字的情况.(这里我们只考虑没有顺序的情况). 公式:C(n,m)=n!/[m!(n-m)!]=n*(n-1)*...*(n-m+1)/[1*2*...*m],如C(5,2)=[5*4]/[1*2]=10. 举例说明:有 1,2,3,4 四个数字,从这四个数字中,任意选择两个数字一共有多少种情况:[1,2], [1,3], [

  • Python实现的简单排列组合算法示例

    本文实例讲述了Python实现的简单排列组合算法.分享给大家供大家参考,具体如下: 1.python语言简单.方便,其内部可以快速实现排列组合算法,下面做简单介绍 2.一个列表数据任意组合 主要是利用自带的库: #_*_ coding:utf-8 _*_ #__author__='dragon' import itertools list1 = [1,2,3,4,5] list2 = [] for i in range(1,len(list1)+1): iter = itertools.comb

随机推荐