在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之前）。

提前感谢。

- bli

---

为什么要使用C++标签？除非你只需要纯算法。但是无论如何，你都必须设置规则，即使你创建了最好的IA，它也会自动为每个集合推导出一个规则。 - Geoffroy

谢谢您的温馨提示，非常抱歉。我只是认为Java和C++很相似，也许C++组里的某个人可以帮助我。 - bli

我会编写Java和C++代码，所以请相信我，它们非常、非常不同。只有一些语法和一些面向对象的概念是相同的 :) - Geoffroy

@bli，你需要的是“偏序”。 - obataku

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.

- user377628

---

交换数值多次后，1将在第3次之后被交换，2将在第4次之后被交换。 - bli

@bli 我不明白你的意思。能否详细说明一下？ - user377628

经过修改后，它可以工作了，非常感谢。问题是：我有一个序列，例如：1 2 3 4，我需要将所有的序列推广到满足约束条件（i必须在i+2之前）：例如1必须在3之前，2必须在4之前。 - bli

@bli 我编辑了我的回答，但我不知道那是否对你有所帮助。那是你想要的吗？ - user377628

Answer 2

这里定义的是偏序关系。您希望生成一个仍满足偏序关系的随机排列，即一个随机线性扩展。

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

"通过转置产生偏序的线性扩展"中涵盖的一种方法涉及以类似于 Hassan 的解决方案的方式交换集合中相邻元素。这似乎是解决手头局部问题的一种有效方式。

- obataku

Answer 3

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

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

当您获得结果后，可以检查您的约束是否匹配，然后打印出另一个列表。可能会像这样：

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

虽然不是最优雅的解决方案，但我认为它应该能够工作。对于小型输入集，效率不会太低。

- RNJ