f# - "Ordered power set"/"Graph coloring"套

Question

我希望在 Ocaml 中完成以下操作，但 ex F# 中的答案可以让我有足够的洞察力来自己进行转换。

安 订购电源组 (从最大组到最小组)将使我更进一步解决下面的问题，这是我理想中想要解决的问题。

对于低效的图形着色，我需要一个函数，它给我以下内容:

f({a,b,c,d}):

{{a,b,c,d}}
{{a,b,c},{d}}
{{a,b,d},{c}}
{{a,c,d},{b}}
{{b,c,d},{a}}
{{a,b},{c,d}}
{{a,c},{b,d}}
{{a,d},{b,c}}
{{a},{b,c},{d}}
{{a},{b},{c,d}}
{{a},{b,d},{c}}
...
{{a},{b},{c},{d}}

作为集合列表(或者更好，作为一个惰性列表/集合枚举)

所以我希望所有变量都在某个集合中表示。但我希望它有序，所以我先得到集合最少的那个，最后得到所有变量都在一个集合中的那个。

我有一个类似这样的解决方案:f: Take powerset -> iterate -> apply f on the rest <- sort the whole list of possibilities
但我想避免对指数列表进行排序。希望我可以用一个懒惰的列表来做到这一点，这样我就可以避免迭代所有的可能性。

Answer 1

鉴于子集的顺序不重要，这是一个更新的解决方案:

let rec splits = function
| [] -> Seq.singleton([],[])
| x::xs ->
    seq { 
        for l1,l2 in splits xs do
            yield x::l1,l2
            yield l1,x::l2
    }

let parts =
    let rec parts' = function
    | 0,[] -> Seq.singleton []
    | _,[] -> Seq.empty
    | 1,l -> Seq.singleton [l]
    | n,x::xs ->
        seq {
            for l1,l2 in splits xs do
            for p in parts'(n-1, l2) do
                yield (x::l1)::p
        }
    fun l -> seq { 
        for k = 1 to List.length l do 
            yield! parts'(k,l) 
    }

这里的想法非常简单。 splits函数提供了将列表分成两组的所有方法。然后计算列表的分区集x::xs我们可以通过 xs 的每个拆分进入 l1,l2 ，并且对于 l2 的每个分区, 添加 x::l1在前。

但是，这不能满足您的订购要求，因此我们将问题进一步分解，并使用嵌套函数 part'计算列表的分区 l准确到n件。然后我们只需要按顺序遍历这些分区列表。