概述：

? 這里你是不是會(huì)說，生成隨機(jī)數(shù)有什么難的？不就是直接使用Java封裝好了的random就行了么？當(dāng)然對(duì)于一般情況下是OK的，而且本文要說明的這些算法也是基于這個(gè)random庫函數(shù)的。

? 本文主要是針對(duì)抽樣這一行為進(jìn)行的，而抽樣本身有一個(gè)隱含的規(guī)則就是不要有重復(fù)數(shù)據(jù)。好了，有了這些說明。你可以先嘗試著用一些自己的想法來實(shí)現(xiàn)不重復(fù)地生成隨機(jī)數(shù)。

本文鏈接：http://blog.csdn.net/lemon_tree12138/article/details/50378102 -- Coding-Naga
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?--轉(zhuǎn)載請(qǐng)注明出處

算法嘗試：

? 一些好的算法出現(xiàn)，往往伴隨著一些不那么好的算法。但是對(duì)于效果不太好的算法，它們普遍有一個(gè)共性，方便理解和實(shí)現(xiàn)。下面是通過一個(gè)循序漸進(jìn)的方式來作一個(gè)簡(jiǎn)單地說明。

第一次嘗試：樸素隨機(jī)算法

? 這個(gè)算法很好理解，就是隨機(jī)！每一次產(chǎn)生一個(gè)隨機(jī)數(shù)，并加入集合。

private void simpleRandom(int start, int end, int count) {System.out.println("樸素隨機(jī)算法：");StringBuffer buffer = new StringBuffer();for (int i = 0; i < count; i++) {int random = NumberUtils.randomInteger(start, end);buffer.append(i == 0 ? ("[" + random) : (", " + random));}buffer.append("]");System.out.println(buffer);}

第二次嘗試：檢查存在性隨機(jī)算法

? 我們知道上面的方法有一個(gè)問題，就是可能會(huì)有重復(fù)數(shù)據(jù)。于是，我們就想到，在生成一個(gè)隨機(jī)數(shù)的時(shí)候進(jìn)行檢查一下這個(gè)數(shù)是不是已經(jīng)存在了，如果存在了就重新生成。

private void checkRandom(int start, int end, int count) {System.out.println("檢查存在性隨機(jī)算法：");StringBuffer buffer = new StringBuffer();List<Integer> save = new ArrayList<>();for (int i = 0; i < count; i++) {int random = NumberUtils.randomInteger(start, end);if (exits(save, random)) {i--;continue;}save.add(random);buffer.append(i == 0 ? ("[" + random) : (", " + random));}buffer.append("]");System.out.println(buffer);}

第三次嘗試：元素移除隨機(jī)算法

? 上面的算法已經(jīng)解決了數(shù)據(jù)重復(fù)的問題。不過，有一個(gè)很糟糕的問題就是可能我們要花費(fèi)很長(zhǎng)的時(shí)間來生成抽樣隨機(jī)數(shù)（這個(gè)要看臉了。。。。）。

? 不過，這里我們有了新想法。那就是在一個(gè)集合中去隨機(jī)一個(gè)數(shù)，當(dāng)這個(gè)被選中的時(shí)候就remove掉，那么下次再隨機(jī)的時(shí)候是不是就不會(huì)再隨機(jī)到這個(gè)數(shù)了？這樣就很好地解決了隨機(jī)數(shù)的重復(fù)問題。代碼如下：

private void removeRandom(int start, int end, int count) {System.out.println("元素移除隨機(jī)算法：");StringBuffer buffer = new StringBuffer();List<Integer> numbers = initList(start, end);for (int i = 0; i < count; i++) {int random = NumberUtils.randomInteger(count - i);buffer.append(i == 0 ? ("[" + numbers.get(random)) : (", " + numbers.get(random)));numbers.remove(random);}buffer.append("]");System.out.println(buffer);}

第四次嘗試：狀態(tài)轉(zhuǎn)移隨機(jī)算法

? 在我之前的很多博客中，就有一些是算法中的狀態(tài)轉(zhuǎn)移過程。而狀態(tài)的轉(zhuǎn)移也是我最喜歡的算法之一。下面的圖-1中標(biāo)注了隨機(jī)數(shù)的取值范圍，序列中的橙色數(shù)字是結(jié)果中的隨機(jī)序列。最下方的序列中有一些虛線的箭頭，代表了狀態(tài)的轉(zhuǎn)移。

圖-1?基于狀態(tài)轉(zhuǎn)移的抽樣隨機(jī)數(shù)生成算法

實(shí)現(xiàn)代碼：

private void statusRandom(int start, int end, int count) {System.out.println("狀態(tài)轉(zhuǎn)移隨機(jī)算法：");StringBuffer buffer = new StringBuffer();int[] status = new int[end + 1];for (int i = 0; i < count; i++) {int random = NumberUtils.randomInteger(start, end);System.err.println(random);if (status[random] == 0) {buffer.append(i == 0 ? ("[" + random) : (", " + random));status[random] = random == end ? start : (random + 1); // 不可能有在start之前的數(shù)字} else {// 狀態(tài)轉(zhuǎn)移int index = random;do {index = status[index];} while (status[index] != 0);buffer.append(i == 0 ? ("[" + index) : (", " + index));status[index] = index == end ? start : (index + 1); // 不可能有在start之前的數(shù)字}}buffer.append("]");System.out.println(buffer);}

第五次嘗試：遞歸Floyd隨機(jī)算法

? Floyd算法說到底也是一種狀態(tài)的轉(zhuǎn)移過程。該算法會(huì)要求輸入一個(gè)List或是array來保存已經(jīng)確定的隨機(jī)數(shù)。顧名思義，這里我會(huì)用到遞歸的解法。在遞歸的過程中，我們把第i個(gè)隨機(jī)數(shù)的狀態(tài)轉(zhuǎn)移到了第i-1個(gè)隨機(jī)身上了。代碼如下：

private List<Integer> simpleFloyd(List<Integer> list, int count, int start, int end) {if (count == 0) {return list;}list = simpleFloyd(list, count - 1, start, end - 1);int random = NumberUtils.randomInteger(start, end);if (list.contains(random)) {list.add(end);} else {list.add(random);}return list;}

第六次嘗試：迭代Floyd隨機(jī)算法

? 思路與上面的遞歸Floyd隨機(jī)算法是相似的，不過，這里我們加入了一個(gè)變量來做優(yōu)化。就不需要再去遞歸了。代碼如下：

private List<Integer> iterationFloyd(int start, int end, int count) {System.out.println("迭代Floyd隨機(jī)算法：");List<Integer> list = new ArrayList<>();for (int i = end - count + 1; i < end; i++) {int random = NumberUtils.randomInteger(start, i);if (list.contains(random)) {list.add(i);} else {list.add(random);}}return list;}

測(cè)試結(jié)果：

圖-2 隨機(jī)數(shù)生成算法測(cè)試結(jié)果

? 在上面的測(cè)試結(jié)果中，我們可以很明顯地看出樸素隨機(jī)算法不僅有重復(fù)數(shù)據(jù)，而且還是最耗時(shí)的。所以，在抽樣的隨機(jī)數(shù)生成時(shí)，避免使用這一算法。而在后幾種算法中，狀態(tài)轉(zhuǎn)移隨機(jī)算法最佳，迭代Floyd隨機(jī)算法次之。這個(gè)可以根據(jù)個(gè)人偏愛來做選擇。

總結(jié)

以上是生活随笔為你收集整理的算法：关于生成抽样随机数的这些算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。