Наборы "Упорядоченный блок питания" / "Раскраска графа"

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 частей , Тогда нам просто нужно перебрать эти списки разделов по порядку.

Answer 2

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 = ()

Если вы хотите выполнить обратную последовательность, то ...

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

изменить на

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

результат:

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']]

Answer 3

Вот быстрая идея.

Один хорошо известный трюк для ленивого генерирования набора мощности набора размера N состоит в итерации каждого числа от 0 до (2 ^ N) -1, учитывая его двоичное представление. Каждая итерация создает раздел: вы помещаете i-й элемент набора в текущий раздел, если i-тая цифра текущего числа равна 1.

Вы можете сделать то же самое в вашем случае: раздел P задается не двоичным числом ниже 2 ^ N, а числом ниже N ^ N в базе N. Теперь трюк, чтобы получить разделы с помощью сначала наименьший компонент:

• первая итерация до 2 ^ N (это дает вам разделы на 2 компонента)
• затем повторяем до 3 ^ N, отклоняя числа, которые не имеют 0, a 1 и a 2 в их представлении (это исключает ранее созданные разделы)
• , затем итерация до 4 ^ N, принимая только числа со всеми 4 различными цифрами
• и т. Д. До N ^ N

Очевидно, это заставляет вас манипулировать довольно большими числами. Вам не нужно кодировать их как целые числа / bignum. Например, в случае с powerset список логических значений также хорош. Эта же идея может быть повторно использована в случае раздела. Более того, K-арные представления двух последовательных чисел близки, так что вы, вероятно, можете кэшировать некоторую информацию для получения более эффективного алгоритма:

• вы можете кэшировать часть вашего текущего разбиения (скажем, вы можете представить текущий раздел как массив списков и просто деструктивно обновить несколько цифр, которые меняются)
• вы можете кэшировать информацию о том, какие цифры в настоящее время присутствуют в числе (чтобы быстро узнать, видели ли вы такое число в предыдущей итерации)

Довольно наивно и пока не предложено никакого кода, извините, но я надеюсь, что моя идея ясна, и вы можете сделать из этого что-то полезное. Люди, которые знают, конечно, имеют более прямые идеи.

В частности, может быть умный способ узнать, использует ли число ниже K ^ N все K цифр своего K-арного представления. Например, вы знаете, что ни одно число ниже K ^ (K-1) не имеет (у них меньше K цифр).