在迭代給定<code>N</code>元件（比方說<code>std::vector</code>或<code>T*</code>）的序列隨機順序

陣列之上，是否有遍歷其以隨機順序元素，訪問每個元件恰好一次任何有效的方法。該解決方案必須避免用混洗索引創建附加數組。在迭代給定<code>N</code>元件（比方說<code>std::vector</code>或<code>T*</code>）的序列隨機順序

編輯：

此外，我們需要能夠跟蹤原來的指數

來源

2013-09-24 Oleg Shirokikh

這是否意味着您根本無法擁有額外的空間，或者只是無法使用預先生成的permutati上？ – Leeor

使用['std :: shuffle']（http://en.cppreference.com/w/cpp/algorithm/random_shuffle），然後從開始到結束迭代。 – Praetorian

Leeor，我試圖找到一種方式如何隨機迭代元素，沒有額外的內存使用，並且仍然能夠跟蹤原始索引 –

使用std::random_shuffle，所以你的代碼會是這樣的：

std::random_shuffle (myvector.begin(), myvector.end()); // in place no extra array 
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it) 
    std::cout << ' ' << *it;

來源

2013-09-24 23:58:09

謝謝，約翰。對不起，我忘了提及我需要知道正在處理的元素的原始索引。謝謝！ –

@ user2028058：爲您的數據創建一個索引向量，然後對其進行隨機掃描，然後遍歷整理後的索引並檢索數據的相應元素。 – beldaz

@beldaz：這肯定會起作用，但問題是如果儘可能避免額外的內存使用（對於索引）。謝謝 –

嗯，我不是在限制使得額外的陣列完全清楚。但基本上，我們隨機生成一個索引，然後重複，如果我們已經命中了一個索引就會重新生成索引。這不一定有效。但是，我猜測這個界限肯定在O（n^2）和O（n！）之間（可能是（O（n^n））。通過一些工作，我們可以清理它並得到。勢必幾乎總是落在N^2

來源

2013-09-24 23:56:15

這太無效了:)但是，謝謝，無論如何！ –

不是特別亂，但鑑於你的限制，你離開了幾個選項

。

A is the array 
S is the size of the array 
Generate a random prime number (P), such that P > S 
Q = P % S 
for i = 1 to S 
    process A[Q] 
    Q = (Q + P) % S

來源

2013-09-25 00:44:42

是否有保證Q會完全覆蓋A的所有元素？ –

@ user2028058：是的，會的。 –

我仍然試圖弄清楚爲什麼以及它如何工作。我不是真的數學。謝謝！ – WoLfulus

在迭代給定<code>N</code>元件（比方說<code>std::vector</code>或<code>T*</code>）的序列隨機順序

回答

相關問題