Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
0xbitboy opened this issue Jan 9, 2019 · 2 comments

Comments

@0xbitboy
Copy link
Owner

0xbitboy commented Jan 9, 2019

业务需求描述

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

分析

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

0xbitboy commented Jan 9, 2019

给定一个长度为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
Copy link
Owner Author

//获取凌晨的秒数
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());

@0xbitboy 0xbitboy reopened this Jan 20, 2019
Repository owner deleted a comment from milosavidev Feb 2, 2024
Repository owner deleted a comment from boboPrem1 Feb 14, 2024
Repository owner deleted a comment Feb 21, 2024
Repository owner deleted a comment from ericssonxiao Feb 21, 2024
Repository owner deleted a comment Feb 21, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants
@0xbitboy and others