字符串组合高效算法代码,Java代码库,德仔网

代码语言
代码分类
【Java】字符串组合高效算法
作者:鬼目 / 发布于2013/10/11/ 537

	竞彩项目中，对选择的多组比赛进行组合过关和赛果组合拆分。
	这是一个对字符串组合算法的示例，使用选号标记移位算法和笛卡尔积进行计算，避免使用递归，效率极高。

	可用于竞彩组合过关拆分，数字彩复式票开奖等业务逻辑。

	AB#CD#EFG#HIJK#LMN#OPQ#RST#UVW#XYZ
	全组合184319个，60ms

	移位算法的好处是，其运算时间和组合结果的总数量成正比，而不会向递归那样成指数增长；因为它是对标志位遍历，对内存资源的消耗也不依赖于组合原子的大小，也只和结果成正比。

	

	import java.util.ArrayList;

	public class GenCom
	{
	//组合算法+笛卡尔积
	
	//计算字符串笛卡尔积(一维数组乘积)
	//使用堆栈算法，不使用递归
	private static void Descartes(ArrayList<String>str_list, ArrayList<String>result)
	{
	 ArrayList<char[]> result_char_list = new ArrayList<char[]>();
	
	 int index = 0;
	
	 while(index < str_list.size())
	 {
	 String cur_str = str_list.get(index);
	
	 if (index == 0)
	 {
	 for (int i=0; i<cur_str.length();++i)
	 {
	 char[] tmp = new char[str_list.size()];
	 tmp[index] = cur_str.charAt(i);
	 result_char_list.add(tmp);
	 }
	 }
	 else
	 {
	 ArrayList<char[]> tmp_char_list =(ArrayList<char[]>) result_char_list.clone();
	 result_char_list.clear();
	
	 for (int i=0; i<tmp_char_list.size(); ++i)
	 {
	 for (int k=0; k<cur_str.length();++k)
	 {
	 char [] tmp = tmp_char_list.get(i);
	 tmp[index] = cur_str.charAt(k);
	
	 result_char_list.add(tmp.clone());
	 }
	 }
	 }
	 index++;
	 }
	
	 for (int i=0; i<result_char_list.size();++i)
	 {
	 result.add(String.valueOf(result_char_list.get(i)));
	 }
	}
	
	//按标志位组合字符串
	private static void MakeCom(String[] str_list, boolean[] flags, ArrayList<String> result)
	{
	 ArrayList<String> choice_str = new ArrayList<String>();
	
	 for (int i=0; i<str_list.length; ++i)
	 {
	 if (flags[i] == true)
	 {
	 choice_str.add(str_list[i]);
	 }
	 }
	
	 //选择完，计算笛卡尔积
	 Descartes(choice_str, result);
	}
	
	//组合算法,n为串数
	//核心算法:选号标记移位算法(选择该位为true,不选为false)，选号标记总最左(栈底)开始，循环移至最右(栈顶)。
	//移动选号位的选择：从最左边(栈底)起向右(栈顶)查询，最近一个上位有空位(false)的选号位(true)
	//将选定的选号位向右移一位(升栈)，左边标记位全部降至左边(栈底)
	//循环上面两个流程至全部选号位移至最右(栈顶)
	public static void GenCom(String[] str_list, int n, ArrayList<String> result)
	{
	 if(n <= 0 || n>str_list.length)
	 {
	 return;
	 }
	
	 //标志数组
	 boolean[] flags = new boolean[str_list.length];
	
	 //初始化前n是选号位
	 for(int i=0; i<n; i++)
	 {
	 flags[i]=true;
	 }
	 //后面都是非选号位
	 for(int i=n; i<str_list.length; i++)
	 {
	 flags[i]=false;
	 }
	
	 //计算初始化组合
	 MakeCom(str_list, flags, result);
	
	 while(true)
	 {
	 int num_count = 0; //从最左边起，连续邻位true true的个数
	 boolean move = false; //是否进行了移位
	
	 //找邻位true false组合
	 for(int i=0; i<str_list.length-1; ++i) //前置1位防越界
	 {
	 if (flags[i] )
	 {
	 if (flags[i+1]) //true true邻位组合，继续向右查找
	 {
	 num_count++;
	 }
	 else //第一个可升位位置
	 {
	 //相邻选号位true false变换为false true
	 //实现升栈
	 flags[i] = false;
	 flags[i+1] = true;
	
	 //左边选号位将至栈底
	 for(int j=0; j<num_count; j++)
	 {
	 flags[j]=true;
	 }
	 for(int j=num_count; j<i; j++)
	 {
	 flags[j]=false;
	 }
	
	 move = true;
	 break;
	 }
	 }
	 }
	
	 if (move)
	 {
	 MakeCom(str_list, flags, result);
	 }
	 else
	 {
	 break;
	 }
	 }
	}

	public static void main(String[] args)
	{
	 String src_str = "ab#c#def#gh#ijk#lmn#opq#rst#uvw#xyz";
	 String[] str_list = src_str.split("#");

	 ArrayList<String> result = new ArrayList<String>();
	
	 for (int i=1; i<=str_list.length; ++i)
	 {
	 GenCom.GenCom(str_list, i, result);
	 }
	
	 for (int i=0; i<result.size(); ++i)
	 {
	 System.out.print( i + ": " + result.get(i) + "\r\n");
	 }
	}
	}
试试其它关键字
　高效算法　
同语言下
可能有用的
鬼目贡献的其它代码(2)