如何利用已知random()函數，求一個1~N的全排列？

已知：一個random()函數可以生成一個(0,1)範圍內的浮點數。

要求：輸入N，利用random()函數，生成一個1至N的全排列。

例如：當輸入N = 4,生成結果可以為1324或3214等等，並保證等概率。

我的想法是，利用random() * N，將每次生成一個隨機數加入到一個vector&ans中（前提是生成的隨機數第一次出現）。直到ans.size() == N時結束程序，輸出結果。

面試官對於我的想法提出了一些意見：例如當N = 5時，已經生成了1324這四個隨機數，而第五個隨機數遲遲不能得到5，很浪費時間。這僅僅是最後一個數而已，倒數第二個數也面臨同樣的問題，以此類推，倒數第三個，第四個……使得代碼整體效率不高。

我當時的想法是如果人為干預生成的隨機數，那就不能保證等概率。

請問大家有一些什麼好的辦法嗎？

---

思路沒錯，不過要略微有一些調整，首先在vector裡面生成1-N的數，然後第一次在1-N當中隨機選一個，然後跟最後一個交換位置；第二次，在1-（N-1）當中隨機選一個，然後跟N-1個交換位置。這樣每次都是生成一次隨機數就可以選出一個隨機元素，而且是均勻的。

如果N非常大，然後是從中選出一個m個元素的排列，可以把vector換成散列表（也就是hash_map或者說unorderedmap）。

---

Fisher-Yates shuffle

---

從 0 到 n 之間選 k 個不重複的數組成一個序列。

編程珠璣里隨機數產生演算法

---

將隨機數賦值a1 a2 … an

將a1 a2 … an 按大小排序並依次輸出a的下標即可

---

演算法導論第五章，先生成一個從1到N的數組A然後下面圖中中間偽代碼部分描述的演算法

將偽代碼第三行改為

swap A[i] with A[i+random()*(N-i)]

---

這個不就是將1-N的數進行隨機排序嗎？簡單啊。

方式一，最簡單的：生成一個1-N的數組list（就按順序擺，沒事），然後使用java裡面Collections的這個方法：

public static void shuffle(List& list)


方式二，多年以前我寫過一個O(n)的演算法「快速獲取[0,n]之間的k個不同的隨機順序的隨機整數」

為了方便查看，把代碼貼過來啦：

/**
* 隨機抽取[0,n)之前的k個不同的數並隨機排序，（k&<=n） * * @param n * @param k * @return 隨機排序的數組，長度為k */ public static int[] getRandomArray(int n, int k) { if (k &> n) {
k = n;
}
int[] rets = new int[k]; // 保存取出的隨機數
int[] array = new int[n];// 定義初始數組
for (int i = 0; i &< n; i++) array[i] = i; Random random = new Random(); for (int j = 0; j &< k; j++) { int index = j + random.nextInt(n - j);// 生成一個[j,n)之間的隨機數，作為數組下標 // 交換array[j]和array[index]，那麼array[0..j]為已經獲取到的隨機數 int temp = array[index]; array[index] = array[j]; array[j] = temp; // 把此次獲取到的隨機數存到rets裡面 rets[j] = temp; } return rets; }

演算法是n中選k個，你改造一下就行啦。

---

對於n，random n次，記錄順序，排個序，對應n到1，再按原來的順序替換浮點數。

演算法渣，提個思路，輕虐。

---

洗牌演算法。

a(1..n)=(1..n)

r=n

while r&>1:

t=random(r)

swap(a(t), a(r))

r--

end

---

題目上說的全排列指的是 提供的數組是全排列的吧。

這樣就成了一個經典洗牌演算法。

洗牌演算法的核心思想是使用原數組交換來完成重洗。並且每個元素遍歷一次

演算法是

i從n到1

Swap(a[i],a[random()%(i+1)])

一個數字只便利一次。因為原數組已有所有元素和順序 隨機交換即可

---

先把所有組合排好共有5！=120種，存到一個matrix，第一列是index，第二列是對應的排列，然後random生成1-120中的某一個數，再去matrix訪問對應的排列。

---

你這題就不清楚

「要求：輸入N，利用random()函數，生成一個1至N的全排列」

這是要全排列

「例如：當輸入N = 4,生成結果可以為1324或3214等等，並保證等概率。」

這只是要一個隨機的亂序結果

「我的想法是，利用random() * N，將每次生成一個隨機數加入到一個vector&ans中（前提是生成的隨機數第一次出現）。直到ans.size() == N時結束程序，輸出結果。」

你的想法實現的只是一種隨機亂序結果。和全排列沒啥關係。

面試官也不知道是對這題本來就很蒙，還是看你按隨機理解的了，就順道問下去了（或者你記錯題了）

回到你的題干，全靠隨機不行，就需要自已的規則

ps: 只是隨機，和全排列沒關係。

思路參考一致性哈希，如果之前已經生成過，則取某方向的最近的一個值（這裡的方向是向左），到0處，跳到4，按環狀邏輯處理。

邏輯很簡單，不過因為有這個規則在，4321顯然比1234的概率大，不合題目要求。

還是用老辦法吧，生成一堆範圍內的隨機數（個數隨意），對稱位交換。

/**
* Created by cclient on 16/9/15.
*/

function r(len) {
var obj = {};
var arr = [];
while(arr.length& 0) {
num--;
} else {
num = len - 1;
}
if (!obj[num]) {
arr.push(num);
obj[num] = 1;
key=false;
}
}
}
}
return arr;
}
var arr=r(4);
arr=arr.map(function(item){
return item+1;
})
console.log(arr.join(""));


---

面試官對於我的想法提出了一些意見：例如當N = 5時，已經生成了1324這四個隨機數，而第五個隨機數遲遲不能得到5，很浪費時間。這僅僅是最後一個數而已，倒數第二個數也面臨同樣的問題，以此類推，倒數第三個，第四個……使得代碼整體效率不高。

想吐嘈一下這句話, 因為這句話其實是不太合適的.

目前大部分答主提出的演算法大多是 級別的, 但是, 可以證明, 你的這個演算法在期望意義下的複雜度也是 的, 也就是說, 這個演算法在大多數情況下, 還是比較快的.

由於期望的線性性質, 我們只需要求出生成每一步的期望次數.

對於求出第i個數的期望次數, 記作 , 那麼推倒一下式子就可以得到:

, 其中 是調和級數, 漸進意義下:

摺疊我吧....

---

這個和洗牌原理是一樣的。

方法一：比如N=5，

然後就生成 包含1，2，3，4，5的數字

然後隨機1-5之間的數字比如3，

那麼那出第3個數字3

然後3從集合裡面拿掉剩下

1，2，4，5

然後隨機1-4之間的數字比如4

那麼就取出來第4個數字5

然後把5這個數從集合裡面拿掉

依次取到裡面沒有數為止。

----

如果牌的數量不多的情況下，數組的數據結構怎麼定義都無所謂。如果多了那得再好好想想，不要引起太大的性能損失。

方法二：

還是生成一個數組1，2，3，4，5

然後random一個數字，比如3

就把1和3調換 結果位 32145

然後到2再random一個數字，比如4

那麼吧2和4調換一下34125

一直循環到最後一個就ok了，這個效率更高一些。

---

遞歸。

突然覺得複雜度可以更小。。修改下答案。

1.對一個順序序列(例如1:N)，若規模為1，將其放入最終解，否則隨機生成其中一個的數R(用正向取整)，放入最終解。

2.若R將序列分為將兩部分，則跳到第3步

否則跳到第1步。

3.對這兩部分序列，分別回到第1步。

---

先產生12345的數列，然後利用random打亂順序

---

import Foundation
let n = 10
var a = Array(0...n)
var ans:[Int] = Array(repeating:0, count:a.count)
var count = n
for i in 1...n {
let index = Int(arc4random_uniform(UInt32(count)))+1
ans[i] = a[index]
if(index != count){
swap(a[index],a[count])
}
count -= 1
}
print(ans[1...n])


洗牌演算法？恰好曾經面試的時候也被面試官問過。

這裡你只要把 arc4random 換成你自己的隨機函數就行了。

---

例如，輸入4

生成一個字元串1234

然後random()*4取整，得到字元串的某一位，記錄下來，將這個位從字元串剔除。

然後再random()*3取整，得到剩餘字元串的某一位，記錄下來。

……以此類推。

最後得到一個全排列。

還有其他優化點，字元串改成別的也可以，例如list什麼的。

---

有個基本思路，這是一個摸球球的問題:

紙箱里有編號1到N的球球，每次從面摸出一個，依次被摸出的球球編號排列即為所求。

至於用random()函數來實現第M次從N-M+1個球球里隨機摸出一個，不是什麼複雜的事情。

---

var n=5;
var value=new Array();
for(var i=1;i&<=n;i++){ value.push(random()*0+i) } //......

啊？不是腦筋急轉彎？

---

求m=N!，約定階乘的排列方式，然後random()*m

這樣如何？

---

推薦閱讀：