【算法】给定一个长度为m的数组和一个组合大小n，求C(m,n)的所有组合

[0xbitboy]

业务需求描述

• 功能模块每日限免，支持配置 m 个功能，展示 n 个
• 每天显示不同的组合

分析

• 需要一个算法对n个功能，进行一个C(n,m)的组合
• 取每天的凌晨的秒数 hash到不同的组合中。

[0xbitboy]

给定一个长度为m的数组和一个组合大小n，求C(m,n)的所有组合

/**
 * 列表的组合
 * @see <a href="https://leetcode-cn.com/problems/combinations/submissions/">leetcode-Combinations</a>
 * @author liaojiacan
 * @date 2019/1/9
 */
public class Combiner {

	/**
	 * 获取originList的 大小为combinationSize的T元素的所有组合
	 * @param originList
	 * @param combinationSize
	 * @param <T>
	 * @return
	 */
	public static <T> List<List<T>> combine(List<T> originList, int combinationSize){
		Assert.check(originList.size() >=combinationSize,"originList size should greater than combinationSize");
		if(originList.size() == combinationSize ){
			List<List<T>> result  = new ArrayList<>(1);
			result.add(originList);
			return result;
		}
		List<List<T>> combinations = new ArrayList<>(calculateCombinationNum(originList.size(),combinationSize));
		combine(combinations,originList,combinationSize,0,new ArrayList<>(combinationSize));
		return combinations;
	}


	private static <T> void combine(List<List<T>> combinations,List<T> originList,int combinationSize,int elementIndex,List<T> combination){

		if( combinationSize == 0 ){
			combinations.add(new ArrayList<>(combination));
			return;
		}

		for( int i = elementIndex ; i <= originList.size()-combinationSize ; i++ ){
			combination.add(originList.get(i));
			combine(combinations,originList,combinationSize-1,i+1,combination);
			combination.remove(combination.size()-1);
		}

	}

	/**
	 * 计算组合的近视值 C(m,n)
	 * @see <a href="https://program-dog.blogspot.com/2017/05/stirlingapproximation.html">stirling</a>
	 * @see <a href="https://blog.csdn.net/uself/article/details/54575930">组合的近似值算法</a>
	 * @param originElementSize
	 * @param combinationSize
	 * @return
	 */
	private static int calculateCombinationNum(int originElementSize,int combinationSize){
		int m = originElementSize;
		int n = combinationSize;
		return (int) Math.ceil((1/Math.sqrt(2*Math.PI))*Math.sqrt(m/(n*(m-n)))*(Math.pow(m,m)/Math.pow(n,n))*Math.pow((m-n),(n-m)));
	}

}

[0xbitboy]

//获取凌晨的秒数
ZonedDateTime localDateTime = Instant.now().atZone(ZoneId.systemDefault()).toLocalDate().atStartOfDay(ZoneId.systemDefault());
Date todayStartTime = Date.from(localDateTime.toInstant());
int index = (int) ((todayStartTime.getTime() / 1000) % combinations.size());