基于用户偏好最大化查找满足黑盒校验的列表排列的算法求解问题

我有一个函数f，它接收一个list类型的元素列表作为唯一参数，若该列表的元素排序符合要求则返回true，否则返回false。

• 已知列表l至少存在1个或多个排列可以让f(l)返回true。
• 函数f是黑盒（无源码），且列表l存储的元素类型为未知泛型。
• p是列表l的一个按用户偏好排序的排列，优先级最高的元素位于索引0，优先级最低的元素位于索引l.size()-1，且p一定包含l的所有元素。
• 目标是找到l的一个排列p_accepted，要求满足f(p_accepted)返回true，且该排列的用户偏好优先级最大化。

示例 #

给定 l = [a, b, c, d, e, f]
给定 p = [c, a, f, b, e, d]
给定 f([ a, b, c, d, e, f ]) = false
给定 f([ c, a, f, b, e, d ]) = false
给定 f([ d, e, b, f, a, c ]) = true
给定 f([ f, e, d, c, b, a ]) = true
给定 f([ c, b, f, a, d, e ]) = true
给定 f([ a, c, f, b, e, d ]) = true
给定 f([   其余所有排列  ]) = false
预期输出的p_accepted为 [c, b, f, a, d, e]
该排列符合要求的原因是：f(p_accepted)返回true，且不存在其他排列能将用户优先级最高的元素'c'放在更靠前的位置。

补充说明 #

• 列表p一定包含l的所有元素。
• 列表l的元素仅支持身份比较，即通过引用判断相等，可通过l[i] == p[j]判断p中的元素是否存在于l中。
• 列表l的元素不支持自定义大小比较，不存在可以判断a < b的比较函数c，例如c('a', 'b') = 1这类逻辑不通用。

偏好规则补充说明 #

举个便于理解的例子：Alice和Bob需要按顺序共同完成4项任务[任务a, 任务b, 任务c, 任务d]。Alice偏好的执行顺序是[a,b,c,d]，Bob接受的执行顺序只有[a,c,b,d]和[a,d,b,c]两种。此时函数f仅对Bob接受的两个顺序返回true，最优的p_accepted应当以a开头，因为双方都将a放在首位。

注：以上仅为类比，函数f的校验规则并非基于多用户偏好交集。

核心思路 #

采用贪心策略逐位构造最优排列：从左到右确定排列的每一位，每一位都优先选择当前未使用的、用户优先级最高的元素，验证该元素放在当前位置后，剩余元素是否存在合法排列可以和当前前缀拼接得到符合f要求的完整排列。如果验证通过就保留该元素在当前位置，否则尝试下一个优先级的候选元素，直到所有位构造完成。

代码实现（Python） #

from itertools import permutations

def find_optimal_permutation(l, p, f):
    n = len(l)
    used = [False] * n
    res = []
    for _ in range(n):
        # 按用户优先级从高到低遍历未使用的元素
        for i in range(n):
            if not used[i]:
                candidate = p[i]
                # 临时将候选元素加入当前前缀
                res.append(candidate)
                used[i] = True
                # 收集剩余未使用的元素
                remaining = [p[j] for j in range(n) if not used[j]]
                # 验证是否存在剩余元素的排列可以拼接出合法结果
                if has_valid_permutation(res, remaining, f):
                    # 当前候选可行，进入下一位构造
                    break
                else:
                    # 验证不通过，回退
                    res.pop()
                    used[i] = False
    return res

def has_valid_permutation(prefix, remaining, f):
    # 遍历剩余元素的所有排列，拼接前缀后调用f验证
    for suffix in permutations(remaining):
        if f(prefix + list(suffix)):
            return True
    return False

内容的提问来源于stack exchange，提问作者Andrei Matei