“有序电源”/“图色”集。

I want the following to be done in Ocaml but an answer in ex F# could give me enough insight to do the conversion myself.

我希望在Ocaml中完成以下任务，但在前f#中给出的答案可以让我有足够的洞察力来完成转换。

An ordered power set (from biggest set to the smallest) would make me one step further the problem below which is want I ideally want to be solved.

一个有序的幂集(从最大的集合到最小的集合)会使我更进一步，下面的问题是希望我理想的解决。

For a inefficient graph coloring, I need a function which gives me the following:

对于一个低效率的图着色，我需要一个函数，它给出如下:

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}}

as a list of sets (or better, as a lazy list/enum of sets)

作为集合的列表(或者更好，作为一个延迟列表/集合)

So I want all variables to be represented in some set. But I want it ordered so I get the one with fewest sets first and the one where all variables is in a set last.

我希望所有的变量都能在某个集合中表示出来，但我想要它是有序的，所以我先得到最少的集合，然后所有的变量都在最后一个集合中。

I've one solution which is something like this: f: Take powerset -> iterate -> apply f on the rest <- sort the whole list of possibilities

我有一个解决方案，它是这样的:f:取powerset ->迭代->在rest中应用f -对所有可能的列表进行排序。

But I would like to avoid sorting an exponential list. And hopefully I can do it with a lazy list so I avoid iterating all possibilities.

但我想避免对指数列表进行排序。希望我可以用一个懒惰的列表来做，所以我避免重复所有的可能性。

3 个解决方案

#1

let rec comb n l =
  match n, l with
  | 0, _  -> [[]]
  | _, [] -> []
  | n, x::xs -> List.map (fun l -> x ::l) (comb (n - 1) xs) @ (comb n xs)

let listToSingleSetSet xs = List.map (Set.singleton) xs |> set

let set_2Item_merge (set_set:Set<Set<'T>>) =
  seq {
    let arX = Set.toArray set_set
    let choice_list = comb 2 [0..(arX.Length-1)]
    for [x; y] in choice_list do
      yield begin
        set_set
        |> Set.remove arX.[x]
        |> Set.remove arX.[y]
        |> Set.add (arX.[x] + arX.[y])
      end
  }

let partitions xs =
  let set_set = listToSingleSetSet xs
  let rec aux sq =
    let x = Seq.head sq
    if Set.count x = 1
    then
      Seq.singleton x
    else
      Seq.append sq (Seq.map set_2Item_merge sq |> Seq.concat |> Seq.distinct |> aux)
  aux <| Seq.singleton set_set

DEMO

演示

> partitions ['a'..'d'] |> Seq.iter (printfn "%A");;
set [set ['a']; set ['b']; set ['c']; set ['d']]
set [set ['a'; 'b']; set ['c']; set ['d']]
set [set ['a'; 'c']; set ['b']; set ['d']]
set [set ['a'; 'd']; set ['b']; set ['c']]
set [set ['a']; set ['b'; 'c']; set ['d']]
set [set ['a']; set ['b'; 'd']; set ['c']]
set [set ['a']; set ['b']; set ['c'; 'd']]
set [set ['a'; 'b'; 'c']; set ['d']]
set [set ['a'; 'b'; 'd']; set ['c']]
set [set ['a'; 'b']; set ['c'; 'd']]
set [set ['a'; 'c'; 'd']; set ['b']]
set [set ['a'; 'c']; set ['b'; 'd']]
set [set ['a'; 'd']; set ['b'; 'c']]
set [set ['a']; set ['b'; 'c'; 'd']]
set [set ['a'; 'b'; 'c'; 'd']]
val it : unit = ()

If you want reverse seq then ...

如果你想要反向的seq，那么…

Seq.append sq (Seq.map set_2Item_merge sq |> Seq.concat |> Seq.distinct |> aux)

change to

改变

Seq.append (Seq.map set_2Item_merge sq |> Seq.concat |> Seq.distinct |> aux) sq

result:

结果:

set [set ['a'; 'b'; 'c'; 'd']]
set [set ['a'; 'b'; 'c']; set ['d']]
set [set ['a'; 'b'; 'd']; set ['c']]
set [set ['a'; 'b']; set ['c'; 'd']]
set [set ['a'; 'c'; 'd']; set ['b']]
set [set ['a'; 'c']; set ['b'; 'd']]
set [set ['a'; 'd']; set ['b'; 'c']]
set [set ['a']; set ['b'; 'c'; 'd']]
set [set ['a'; 'b']; set ['c']; set ['d']]
set [set ['a'; 'c']; set ['b']; set ['d']]
set [set ['a'; 'd']; set ['b']; set ['c']]
set [set ['a']; set ['b'; 'c']; set ['d']]
set [set ['a']; set ['b'; 'd']; set ['c']]
set [set ['a']; set ['b']; set ['c'; 'd']]
set [set ['a']; set ['b']; set ['c']; set ['d']]

#2

Here's an updated solution, given that the order of subsets is unimportant:

这里有一个更新的解决方案，因为子集的顺序不重要:

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) 
    }

The idea here is pretty straightforward. The splits function gives all ways to partition a list into two sets. Then to calculate the set of partitions of a list x::xs we could go through each split of xs into l1,l2, and for each partition of l2, add x::l1 in front.

这里的想法很简单。拆分函数提供了将列表划分为两组的所有方法。然后计算一个列表x::xs的一组分区，我们可以把xs的每一个分割成l1、l2和l2的每个分区，在前面加x: l1。

However, this won't meet your ordering requirement, so we break the problem down just a little bit further, and use the nested function part' to calculate the partitions of a list l into exactly n pieces. Then we just need to iterate through these lists of partitions in order.

但是，这不会满足您的订购需求，因此我们将问题进一步细分，并使用嵌套的函数部分来计算列表l的分区。然后我们只需要依次遍历这些分区列表。

#3

Here is a quick idea.

这里有一个快速的想法。

One well-known trick to lazily generate the powerset of a set of size N is to iterate each number from 0 to (2^N)-1, considering its binary representation. Each iteration produces a partition : you put the i-th element of the set in the current partition if the i-th digit of the current number is 1.

一个众所周知的方法是延迟生成一组大小为N的powerset，这是为了迭代每个数字从0到(2)-1，考虑到它的二进制表示。每个迭代产生一个分区:如果当前数字的第i个数字为1，则将设置的第i个元素放在当前分区中。

You can do the same in your case: a partition of P is given not by a binary number below 2^N, but by a number below N^N, in base N. Now the trick to get the partitions with the fewest component first is:

你可以做同样的例子:一个分区的P不是由一个二进制数低于2 ^ N,但很多低于N ^ N,N进制下现在的技巧先分区最少的组件是:

• first iterate upto 2^N (this gives you the partitions of 2 components)
• 第一次迭代高达2 ^ N(这给你的分区2组件)
• then iterate upto 3^N, rejecting the numbers that don't have both a 0, a 1 and a 2 in their representation (this rules out the previously produced partitions)
• 然后迭代到3 ^ N,拒绝不都一个0的数字,1和2表示(这排除了以前生产的分区)
• then iterate upto 4^N, taking only numbers with all 4 distinct digits
• 然后迭代upto 4，只取所有4个不同数字的数字。
• etc... upto N^N
• 等等……到N ^

Obviously this makes you manipulate quite large numbers. You do not need to encode them as integers/bignum. For example in the powerset case, a list of booleans is just as good. The same idea could be reused in the partition case. Moreover, the K-ary representation of two consecutive numbers are close, so you can probably cache some information to get a more efficient algorithm:

很明显，这会使你操作相当大的数字。您不需要将它们编码为整数/bignum。例如在powerset的例子中，布尔值的列表也一样好。同样的想法可以在分区案例中重用。另外，两个连续数字的K-ary表示是接近的，所以你可能可以缓存一些信息来得到一个更有效的算法:

• you can cache a part of your current partitioning (say, you could represent the current partition as an array of lists, and just destructively update the few digits that change)
• 您可以缓存当前分区的一部分(比如，您可以将当前分区表示为列表的数组，并对更改的几个数字进行破坏性的更新)
• you can cache the information of which digits are currently present in the number (to know quickly if you have already seen such a number in a previous iteration)
• 您可以缓存当前数字中当前数字的信息(如果您在以前的迭代中已经看到过这样的数字，可以快速地知道)

Quite naive and no code to propose yet, sorry, but I hope my idea is clear and you can make something useful out of it. People That Know certainly have more direct ideas.

很天真，没有代码可以提出，抱歉，但我希望我的想法很清楚，你可以从中做出一些有用的东西。知道的人肯定有更直接的想法。

In particular there may be a clever way to know if a number below K^N uses all K digits its K-ary representation. For example, you know that no number below K^(K-1) does (they have less than K distinct digits).

特别是有一个聪明的办法知道如果数量低于K ^ N使用其所有K-ary K数字表示。例如,你知道没有低于^ K(K - 1)(他们不到K不同的位数)。