订购一组，维护多个定义的分组

Question

由于我很难概括地描述我想要的东西，我尝试举个例子：

给定集合 {x,y,z,d} 和子集 {x,z}、{d,y} 和 {x,y}，我想订购第一个集合 {x,y, z,d} 这样小集合就不会被撕裂（每个集合中的排列并不重要，所以 {x,y} 或 {y,x} 是相同的}。

示例集的长度可以大于此处给出的长度。小集总是最大集的实子集。

我认为如果有一种方法可以说明 ok 集合的这一部分必须保留在这个配置中（x 必须在 y 旁边），但是这部分是任意的。任何建议如何去做？我试着用一棵树来做，但我完全没有解决这个问题:(

Answer 1

我不认为蛮力解决方案缺乏优雅，但它肯定会尝试许多不值得考虑的选项：

from itertools import permutations


def find_ordering(main, subsets):
    for p in permutations(main):
        if all(any(set(p[i:i+len(s)]) == s 
                   for i in range(len(main) - len(s) + 1)) 
               for s in subsets):
            return p


print(find_ordering({1, 2, 3, 4}, [{1, 3}, {4, 2}, {1, 2}]))

结果：

(3, 1, 2, 4)

编辑：好的，这是一个棘手的问题，但这里有一个更聪明的解决方案：

from functools import reduce
from itertools import permutations


def shove(xs: set, yss: list[set]) -> list[set]:
    # move n up to the first part of yss that's not or only partially contained in xs
    # this works because there's no duplicates members among any members of yss
    n = 0
    while n < len(yss) and yss[n] <= xs:
        xs = xs - yss[n]
        n += 1
    # if xs could be shoved into yss entirely
    if not xs:
        return yss
    # if xs covers yss entirely, and some is left over
    elif n >= len(yss):
        return [xs] + yss
    else:
        # h, i, t = xs - yss[n], xs & yss[n], yss[n] - xs
        h, t = xs - (i := yss[n] & xs), yss[n] - i
        # avoid returning empty sets as part of the solution
        return ([h] if h else []) + yss[:n] + ([i] if i else []) + ([t] if t else []) + yss[n+1:]


def find_ordering(main: set, subsets: list[set]) -> list | None:
    # ensure there are no elements in subsets that are not in main
    if not set(reduce(set.union, subsets, set())) <= main:
        return None
    for p in permutations(subsets):
        solution = []
        solution_set = set()
        # try to shove subsets into each other, in order p
        for subset in p:
            solution = shove(subset, solution)
            # if new solution[0] contains elements in the prev solution, there's now duplicates
            if solution[0] & solution_set:
                break
            solution_set = solution_set.union(solution[0])
        else:
            # if all subsets could be shoved together, it's a solution, stop looking and return
            return [x for xs in solution for x in xs]


print(find_ordering({1, 2, 3, 4}, [{1, 3}, {4, 2}, {1, 2}]))
print(find_ordering({1, 2, 3, 4, 5, 6, 7}, [{1, 3}, {4, 2}, {1, 2}, {4, 5, 6}, {3, 7}]))
print(find_ordering({1, 2, 3, 4, 5, 6, 7}, [{1, 6}, {2, 1, 4}, {7, 3}, {3, 4}, {5, 6}]))

结果：

[4, 2, 1, 3]
[7, 3, 1, 2, 4, 5, 6]
[5, 6, 1, 2, 4, 3, 7]

该方法取决于将子集相互推入的想法。如果您将 {1, 2} 推入 [{2, 3, 4}]，结果是 [{1}, {2}, {3, 4}] - 即固定顺序的集合仍然包含原始集合中的分组。 3 和 4 仍然可以改变位置并且顺序将保持不变，但是 none 集合可以改变位置或者顺序被破坏。 shove() 函数执行此操作。推入时，它永远不会改变列表中集合的顺序，但它会忽略集合中元素的顺序进行匹配（如预期的那样）。

find_ordering() 函数使用 shove 尝试以每个可能的顺序将子集推入彼此（使用子集的排列）。

如果扩展解决方案中的第一个集合（在推动之后）包含解决方案中已经存在的任何元素，则意味着解决方案中现在有一个副本并且它不会起作用，因此它会继续下一个排列。

在开始 find_ordering() 之前，它会检查子集是否实际上仅由 main 的元素组成，否则它会尝试所有的元素而无法找到解决方案。在这种情况下，或者如果排列无效，函数 returns None.

这是一个有趣的问题，谢谢。如果您发现此解决方案有任何问题，请告诉我。

编辑：您正确地确定了解决方案的问题 - 原来有 3 个问题，但我认为这个更好。孩子们不要喝酒和写代码。

订购一组，维护多个定义的分组

Order a set, maintaining multiple defined groupings

python

set