假设有100个数字 代表100种不同的物品
每次随机取其中一个使用
使用频率越高的 下次循环取用的时候 随机到这个数的机率就更大。。
反之随机到的机率就越小。。
比如 1234567890 9号在10次随机取中 被抽到 5次 3被抽到3次 7被抽1次 4=1 1=1
他们在第11次随机抽取的 概率 大概为 93“741”25680 大概是这么个排位。
求这个解决思路。。
741是同概率级别的 都被抽过1次 有限概率比后面5位高。。
------解决方案--------------------
- Java code
Map<String, Integer> map = new HashMap<String, Integer>(); List<String> names = new ArrayList<String>() ; for (int i = 0; i < 10; i++) {//装数据 map.put(""+i, 1) ; names.add(i+"") ; } for (int j = 0; j< 20; j++) { int i = 0 ; for (String key : names) { i =i + map.get(key) ; } Random random = new Random() ; int index = random.nextInt(i) ; i = 0 ; String name ="" ; for (String key : names) { if(i>=index) { name = key ; break ; } i =i + map.get(key) ; } System.out.println("取出的name"+ name); map.put(name, map.get(name)+1) ; System.out.println(map); }
------解决方案--------------------
5L和10L思路一样，线性分布会影响性能，随着随机次数的增加，list的size就会越来越大，最后会耗尽内存的，所以不可取，4L说的权值管理，实际上就是概率区间分布管理，实现起来也很简单
- Java code
//初始化处理int[] num = {...}; //100个数字TreeMap<Integer, List<Integer>> prob = new TreeMap<Integer, List<Integer>>(); //权值管理表prob.put(1, new ArraysList()); //初始化权值为1for (int n : num) { prob.get(1).add(n); //把100个数字加入权值管理表}//取随机数处理TreeMap<Integer, Integer> tmp = new TreeMap<Integer, Integer>(); //权值区间分布整理，用于查找权值（避免遍历）int sum = 0; //权值求和for (int n : map.keySet()) { tmp.put(sum, n); //权值区间分布 sum += n; //求权值总和}int p = (int)(Math.random()*sum); //取[0,sum)之间的随机数int key = tmp.lowerEntry(p).getValue(); //取随机数p所在区间的权值管理表的keyList<Integer> list = prob.get(key); //key所对应的数字列表信息int index = (int)(Math.random()*list.size()); //随机获取数字列表的一个位置int ran = list.remove(index); //获取随机位置的数字//刷新权值管理表信息if (list.size()==0) { prob.remove(key); //如果权值对应的数字列表信息没有，则删除权值}if (!prob.containsKey(key+1)) { //权值+1作为key，如果这样的权值不存在 prob.put(key+1, new ArrayList<Integer>()); //则加入权值管理表}prob.get(key+1).add(ran); //把随机数放到权值增加的数字列表中
------解决方案--------------------
午休
- Java code
public static void main(String[] args) { //随机数组 int array[]=new int[]{1,2,3,4,5}; //对应权值 int temp[]=new int[] {1,1,1,1,1}; //看看对应的区间 for(int i=0;i<temp.length;i++){ System.out.println(i+1+": "+(i==0?1:(getEnd(temp,i-1)+1))+"---"+getEnd(temp,i)); } //随机空间为 1---getEnd(temp,temp.length-1)+1 int randomNum=new Random().nextInt(getEnd(temp,temp.length-1)+1); int index=getIndex(temp,0,randomNum);//对应索引 System.out.println(randomNum+"---"+array[index]); //修改权值 temp[index]+=1; } //索引对应的区间结尾 private static int getEnd(int[] array,int index){ if(index<=0) return array[0]; return array[index]+getEnd(array,index-1); } //某值随机值对应的索引位置 private static int getIndex(int[] array,int index ,int num){ if((num-=array[index])<=0||index==array.length-1) return index; return getIndex(array,++index, num); }