algorithm - 算法：按偏好生成列表排列

Question

我有一个函数f，它接受一个list项目作为它的单个参数，true如果项目的排序被接受或者项目false的排序不被接受，则返回。

至少存在一个或多个返回 true的列表l排列。f(l)

函数f是一个黑盒子（我们没有它的源代码），列表l所包含的元素的类型也是未知的或通用的。

p是l根据用户偏好的列表排列。最喜欢的项目有索引0最不喜欢的项目有索引l.size()-1 listp将始终包含 list 的所有元素l。

目标是找到l让我们称之为的排列，p_accepted其中f(p_accepted)返回 true 并且偏好p最大化。

这是一个例子

given l = [a, b, c, d, e, f]
given p = [c, a, f, b, e, d]

given f([ a, b, c, d, e, f ]) = false
given f([ c, a, f, b, e, d ]) = false
given f([ d, e, b, f, a, c ]) = true
given f([ f, e, d, c, b, a ]) = true
given f([ c, b, f, a, d, e ]) = true
given f([ a, c, f, b, e, d ]) = true
given f([   anything else  ]) = false

the expected output for p_accepted is [c, b, f, a, d, e]
it is accepted because f(p_accepted) returns true and no other permutation of l ranks the item 'c' as high. item 'c' is the most preferred by the user since it has index 0

接受伪代码或任何语言的实现。

[编辑]

澄清

listp将始终包含 list 的所有元素l

列表l项只能通过身份进行比较，即：通过引用，因此p可以在列表中找到列表中l的项目l[i] == p[j]

列表l项不能总是像示例中那样比较，其中比较函数c可能确定a < bie: c('a', 'b') = 1。

[编辑 2] 更好地理解偏好

想象一下 Alice 和 Bob 被迫按顺序同时执行 4 个任务。[任务a，任务b，任务c，任务d]。Alice 有一个优先顺序来执行任务 [a,b,c,d]。Bob 有两个优先顺序来执行任务 [a,c,b,d]，[a,d,b,c]。如果您是 Alice，该函数f将仅对 Bob 的偏好 [a,c,b,d] 和 [a,d,b,c] 返回 true，因为两者都喜欢首先执行任务 ap_accepted应该以 a 开头。

请注意，这是一个类比函数f，不接受基于多个用户的订单偏好的排列。

标签： algorithm