What I have is a vector (n = 4 in the example):
我有一个向量(n = 4)
x = '0123';
What I want is a vector y of the same size of x and with the same elements as in x in different order:
我想要的是一个向量y，它的大小和x的元素相同，但顺序不同:
y = ['0123'; '0132'; '0213'; '0231'; '0312'; '0321'; '1023'; '1032'; '1203'; '1302'; '2013'; '2031'; '2103'; '2301'];
y(ceil(rand * numel(y(:, 1))), :)
i.e. a permutation such that each element in y is allowed to randomly change no more than k positions with respect to its original position in x (k = 2 in the example). The probability distribution must be uniform (i.e. each permutation must be equally likely to occur).
即一个排列，使得y中的每一个元素都可以随机的改变k个位置，在x (k = 2)的位置。概率分布必须是均匀的(也就是说，每个排列发生的概率必须是相等的)。
An obvious but inefficient way to do it is of course to find a random unconstrained permutation and check ex post whether or not this happens to respect the constraint. For small vectors you can find all the permutations, delete those that are not allowed and randomly pick among the remaining ones. Any idea about how to do the same more efficiently, for example by actually swapping the elements?
一种明显但低效的方法当然是找到一个随机的无约束排列，并检查ex post是否碰巧符合约束条件。对于小的向量，你可以找到所有的排列，删除那些不允许的排列，然后在剩下的排列中随机选择。你知道如何更有效地做同样的事情吗，例如通过交换元素?
2 个解决方案
#1
1
I don't see any approach other than the rejection method that you mention. However, instead of listing all allowed permutations and then picking one, it's more efficient to avoid that listing. Thus, you can randomly generate a permutation, check if it's valid, and repeat if it's not:
除了你提到的拒绝方法之外，我没有看到任何方法。然而，与其列出所有允许的排列然后选择一个，不如避免列出一个更有效。因此，您可以随机生成一个置换，检查它是否有效，如果不是，则重复:
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);
#2
3
Generating all the permutations can be done easily using constraint programming. Here is a short model using MiniZinc for the above example (note that we assume that x will contain n different values here):
使用约束编程可以轻松地生成所有的排列。这里有一个使用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)];
In most cases, constraint programming systems have the possibility to use a random search. However, this would not give you a uniform distribution of the results. Using CP will however generate all valid permutations more efficiently than the naive method (generate and test for validity).
在大多数情况下，约束编程系统都可以使用随机搜索。然而，这并不能给出结果的统一分布。然而，使用CP会比使用naive方法更有效地生成所有有效的排列(生成并测试有效性)。
If you need to generate a random permutation of your kind efficiently, I think that it would be possible to modify the standard Fisher-Yates shuffle to handle it directly. The standard algorithm uses the rest of the array to choose the next value from, and chooses the value with a probability distribution that is uniform. It should be possible to keep a list of only the currently valid choices, and to change the probability distribution of the values to match the desired output.
如果您需要高效地生成同类的随机排列，我认为可以修改标准Fisher-Yates shuffle来直接处理它。标准算法使用数组的其余部分来选择下一个值，并选择具有均匀概率分布的值。应该可以只保留当前有效选项的列表，并更改值的概率分布以匹配所需的输出。
#1
1
I don't see any approach other than the rejection method that you mention. However, instead of listing all allowed permutations and then picking one, it's more efficient to avoid that listing. Thus, you can randomly generate a permutation, check if it's valid, and repeat if it's not:
除了你提到的拒绝方法之外，我没有看到任何方法。然而，与其列出所有允许的排列然后选择一个，不如避免列出一个更有效。因此，您可以随机生成一个置换，检查它是否有效，如果不是，则重复:
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);
#2
3
Generating all the permutations can be done easily using constraint programming. Here is a short model using MiniZinc for the above example (note that we assume that x will contain n different values here):
使用约束编程可以轻松地生成所有的排列。这里有一个使用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)];
In most cases, constraint programming systems have the possibility to use a random search. However, this would not give you a uniform distribution of the results. Using CP will however generate all valid permutations more efficiently than the naive method (generate and test for validity).
在大多数情况下，约束编程系统都可以使用随机搜索。然而，这并不能给出结果的统一分布。然而，使用CP会比使用naive方法更有效地生成所有有效的排列(生成并测试有效性)。
If you need to generate a random permutation of your kind efficiently, I think that it would be possible to modify the standard Fisher-Yates shuffle to handle it directly. The standard algorithm uses the rest of the array to choose the next value from, and chooses the value with a probability distribution that is uniform. It should be possible to keep a list of only the currently valid choices, and to change the probability distribution of the values to match the desired output.
如果您需要高效地生成同类的随机排列，我认为可以修改标准Fisher-Yates shuffle来直接处理它。标准算法使用数组的其余部分来选择下一个值，并选择具有均匀概率分布的值。应该可以只保留当前有效选项的列表，并更改值的概率分布以匹配所需的输出。