假设你有一个任意大小的圆桌会议，并且你想让所有的客人大多随机坐在桌子旁，但是有一些关于邻接的规则。
例如：Alice，Bob，Charlie，Dan，Eve，Frank，Gerry和Heidi正在共进晚餐。创建一个随机的座位安排，使爱丽丝不在格里旁边，查理不在弗兰克身边。
到目前为止，因为我很懒惰并且它有效，我一直在通过改组列表然后只是重新洗牌，如果结果违反任何邻接限制。不过，我很幸运，我的“客人名单”很大，我的限制很少，所以失败案例很少见。
我猜测更好的解决方案涉及：
虽然我正在研究它，但我发现自己想知道是否有办法预先检测某个列表的邻接排除是否无法满足。也许通过构建一个“合法”选项树并查看其深度是否<列表的长度？
在不偏置分布的情况下向正被采样的空间添加约束可能非常困难。如果你进行部分回溯，那么你就可以将较早放置的项目权限放在稍后放置的项目上，使得先前放置的项目的分布更接近于（无约束的）随机混乱的预期，同时放大约束对后者的影响 - 放置的。考虑只允许Alice，Yolanda和Zelda坐在Beth旁边的情况。如果你按字母顺序分配座位，当你遇到无法解决的情况时回溯，爱丽丝比其他两个中的任何一个更不可能最终在Beth旁边，因为Beth不太可能最初放在Alice旁边，你的回溯将永远不会让你移动贝丝。
你所谓的“懒惰”被称为rejection sampling，它通常是解决这类问题的首选方法，所以不要卖空。对于你将要拒绝大量空间的情况，有一些拒绝采样的变体，一旦你了解它们就能很好地工作。我使用the Metropolis-Hastings algorithm也有很好的结果，这是（IMO）更容易理解和利用。如果您只需要一个样本，则可以进行老化阶段，然后只进行当前状态。
您没有描述对约束的任何限制。因此，简单的答案是“否”：没有确定解决方案是否存在的方法，没有通过所有允许的序列来寻找满足所有约束的序列。
如果可以表征约束，则可以根据这些属性指示搜索。如果约束都具有适合于形式证明的逻辑属性，那么您将拥有一个系统，在该系统中，您可以通过搜索约束空间而不是N来获得“是/否”结果！蛮力座位搜索的空间。
可能的方法
我们希望首先安排最大的抱怨者：首先解决已知问题，然后再导致座位失败。
seat_next列表初始化为空。seat_next。seat_next流行一个人。seat_next。seat_next为空，请重复步骤2;否则，重复步骤3。仍然需要考虑许多调整元素，具体取决于约束的交互和类型。例如，您可能会根据人们出现的约束数量对人们进行加权;您可能希望对约束进行堆叠或排队，以便在转到下一个约束之前满足一个约束。