置換n個元素由不多於k的位置

交換各要素

x = '0123';

我想是的相同大小的矢量y x和與所述元件相同的元件在不同的階x：

y = ['0123'; '0132'; '0213'; '0231'; '0312'; '0321'; '1023'; '1032'; '1203'; '1302'; '2013'; '2031'; '2103'; '2301']; 
y(ceil(rand * numel(y(:, 1))), :)

即，置換，使得在y中的每個元素被允許相對於隨機改變不大於k的位置更向x中其原來的位置（K =在這個例子中是2）。概率分佈必須是統一的（即每個置換必須同樣可能發生）。

做一個明顯但低效的方法當然是找到一個隨機的無約束排列，並檢查事後是否發生這個約束。對於小型媒介，你可以找到所有的排列組合，刪除那些不允許的組合，然後從剩餘的組合中隨機挑選。有關如何更有效地做到這一點的任何想法，例如通過實際交換元素？

來源

2014-02-10 randomatlabuser

我沒有看到除了您提到的拒收方法之外的任何方法。但是，不要列出所有允許的排列，然後選擇一個排列，而是避免該列表更有效。因此，你可以隨機生成一個置換，檢查它是否有效，重複，如果它不是：

x = '0123'; 
k = 2; 

n = numel(x); 
done = 0; 
while ~done 
    perm = randperm(n); 
    done = all(abs(perm-(1:n)) <= k); %// check condition 
end 
y = x(perm);

來源

2014-02-10 11:52:59

謝謝路易斯，現在看來，這是做這件事的最好方法。如果'n'很小，可能產生允許排列的列表會更快。 – randomatlabuser

歡迎！另外，如果你打算產生許多排列，那麼生成整個列表可能會更好 –

生成所有的排列可以很容易地使用約束編程來完成。下面是使用MiniZinc對於上面的例子（注意，我們假設x將包含這裏n個不同的值）短型號：

include "globals.mzn"; 

int: k = 2; 
int: n = 4; 
array[1..n] of int: x = [0, 1, 2, 3]; 
array[1..n] of var int: y; 

constraint forall(i in 1..n) (
    y[i] in {x[i + offset] | offset in -min(k, i-1)..min(k, n-i)} 
); 

constraint all_different(y); 

solve :: int_search(y, input_order, indomain_min, complete) 
    satisfy; 

output [show(y)];

在大多數情況下，約束編程系統必須使用隨機搜索的可能性。但是，這不會給你一個統一的分配結果。然而，使用CP會比天真的方法（生成和測試有效性）更有效地生成所有有效的排列。

如果您需要高效地生成隨機排列，我認爲可以修改標準Fisher-Yates shuffle來直接處理它。標準算法使用數組的其餘部分從中選擇下一個值，並以統一的概率分佈選擇值。應該只能保留一個僅包含當前有效選項的列表，並更改值的概率分佈以匹配期望的輸出。

來源

2014-02-11 10:18:06 Zayenz

置換n個元素由不多於k的位置

回答

相關問題