Блог

Я хочу, чтобы следующее было выполнено в 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

Но я бы хотел избежать сортировки экспоненциального списка. И, надеюсь, я смогу сделать это с помощью отложенного списка, чтобы избежать повторения всех возможностей.

Вот обновленное решение, учитывая, что порядок подмножеств не имеет значения:

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

 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
  

ДЕМОНСТРАЦИЯ

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

Вот небольшая идея.

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

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

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

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

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

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

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