java - 在java中生成随机顺序但有约束

Question

当我放置一个整数列表时，如何生成另一个随机顺序但有约束？

例如，我将整数 1、2、3、4 放入集合中，当我尝试打印结果时，例如 "1 2 3 4","1 2 4 3","1 3 2 4" ,"2 1 3 4" 或 "2 1 4 3"（1 必须在 3 之前，2 必须在 4 之前）

提前致谢

Answer 1

您可以考虑的一件事是随机交换元素。您可以在集合中选择一个随机位置，然后将该位置的元素与下一个元素交换。这样，您可以防止将 1 与 3 或 2 与 4 交换。您可以重复执行此操作，直到数字被正确打乱：

[1, 2, 3, 4]随机数为 0，与位置 1 的元素交换。

[2, 1, 3, 4]随机数为 1，与位置 2 的元素交换。

元素是 1 和 3，所以不要交换。

[2, 1, 3, 4]随机数为 2，与位置 3 的元素交换。

[2, 1, 4, 3]等等

如果您想概括约束，您可以简单地更改条件。当元素是 1 和 3 或 2 和 4 时（如上面的示例），您可以确保要交换的位置处的两个元素彼此不在 2 之内，而不是拒绝交换，例如if(b==a+2)continue;：

元素是 5 和 7，所以不要交换。

if(7==5+2)continue; // ie don't swap.

Answer 2

您在此处定义的内容称为偏序。您希望生成仍然满足偏序的随机排列，即随机线性扩展。

幸运的是，Java API 指定了Collections.shuffle，它实现了 Fisher-Yates 算法来生成随机排列。不幸的是，标准的 Java 技术 viaCollections.sort是比较排序，因此专注于全序——不像我们想要的偏序。事实上，Java API 缺少我们可以在这里使用的排序算法。

“通过转置生成 Posets 的线性扩展”中介绍的一种方法涉及以类似于 Hassan 的解决方案的方式交换集合中的相邻元素。对于手头的局部问题，这似乎是一种有效的方式。

Answer 3

如果将其用作字符串，则可以使用此答案的算法来交换所有数字

当您输入所有数字时，只需将它们连接在一起即可。无需将它们视为数字或字符串。您要做的就是重新排序它们。

当你得到结果时，你可以检查你的约束是否匹配，然后打印出另一个列表。可能是这样的

private boolean isConstraintSatisfied(String wholeString, String firstNum, String secondNum){
    return wholeString.indexOf(firstNum) <= wholeString.indexOf(secondNum);
}

不是最优雅的解决方案，但我认为它会起作用。对于小型输入集，它不应该太低效。