arrays - 查找数组的所有键唯一排列

Question

我有一个看起来像这样的数组:

[["Sunday", [user1, user2]], ["Sunday", [user1, user4]], ["Monday", [user3, user2]]]

该数组基本上包含给定日期与一对唯一用户的所有排列。我是通过运行得到的

%w[Su Mo Tu We Th Fr Sa].product(User.all_pairs)

其中 User.all_pairs 是每对唯一的用户。

我现在的目标是将这组嵌套数组组合成时间表，这意味着我想找到长度为 7 且具有唯一日期的每个排列。换句话说，我想要每一个潜在的星期。我已经拥有了每一天的潜在用户，并且拥有了每一对潜在的用户，现在我只需要组合它们。

我有一种预感，Array.permutation 方法是我所需要的，但我不确定在这种情况下我将如何使用它。或者我应该使用 Array.product？

Answer 1

如果我没理解错的话，您希望在所有可能的周内每天分配一对用户。你可以这样做:

User.all_pairs.combination(7)

这将为您提供所有可能的方法，让您可以选择 7 对并将它们分配给一周中的几天。但是，如果您要求每一个可能的星期，那么将哪对分配到哪一天也很重要，并且您还必须对这 7 对进行所有排列:

User.all_pairs.combination(7).map{|week| week.permutation().to_a}.flatten(1)

现在这将为您提供所有可能的星期，其中每个星期都表示为包含 7 对的数组。例如，其中一周可能如下所示:

[(user1, user2), (user1, user3), (user2, user3), (user3, user4), (user1, user4), (user2, user4), (user3, user4)]

不过周数会很大!如果你有 n 个用户，你会有 k = n!/2 对，有 p = k!/(7! * (k - 7)!) 选择 7 对的方法和 p * 7! 可能的周数。如果您只有 5 个用户，则可能有 1946482876800 周!不管你打算用它做什么，这都是不可能的。

如果你想找到一周的最佳时间表，你可以尝试做一些贪心算法。