Извлечение листовых путей из n-арного дерева в F # - PullRequest
Новая
       73

Извлечение листовых путей из n-арного дерева в F #

5 голосов
/ 12 ноября 2008

Вдохновленный этим вопросом , я хотел попробовать свои силы в последней обдумать этот вызов , используя F #

Мой подход, вероятно, совершенно не верен, но в ходе решения этой проблемы я пытаюсь получить список всех перестановок цифр 0-9.

Я смотрю на решение этой проблемы с помощью n-арного дерева следующим образом: 

type Node = 
    | Branch of (int * Node list)
    | Leaf of int

Я вполне доволен собой, потому что мне удалось выработать, как создать дерево, которое я хочу.

Моя проблема сейчас в том, что я не могу понять, как пройти по этому дереву и извлечь «путь» к каждому листу в виде целого числа. Меня смущает то, что мне нужно сопоставлять отдельные узлы, но моя «внешняя» функция должна принимать список узлов.

Моя текущая попытка почти делает правильные вещи, за исключением того, что она возвращает мне сумму всех путей ... 

let test = Branch(3, [Branch(2, [Leaf(1)]);Branch(1, [Leaf(2)])])

let rec visitor lst acc = 
    let inner n = 
        match n with
        | Leaf(h) -> acc * 10 + h
        | Branch(h, t) -> visitor t (acc * 10 + h)
    List.map inner lst |> List.sum

visitor [test] 0 //-> gives 633 (which is 321 + 312)

И я даже не уверен, что это хвостовая рекурсия.

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

РЕДАКТИРОВАТЬ: я опубликовал общий алгоритм перестановок в F # здесь .

Ответы [ 2 ]

5 голосов
/ 12 ноября 2008

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

Этот список принимает список в качестве первого аргумента (путь до сих пор) и дерево и возвращает список> тип - это все возможные пути из текущей ветви. 

let rec visitor lst tree = 
  match tree with
  | Branch(n, sub) -> List.collect (visitor (n::lst)) sub
  | Leaf(n) -> [List.rev (n::lst)]

// For example...
> let tr = Branch(1, [Leaf(3); Branch(2, [Leaf(4); Leaf(5)] )]);;
> visitor [] tr;;
val it : int list list = [[1; 3]; [1; 2; 4]; [1; 2; 5]]

В случае с «листом» мы просто добавляем текущий номер в список и возвращаем результат в виде списка, содержащего один список (сначала мы должны изменить его, потому что мы добавляли числа в начало). В случае «Ветви» мы добавляем «n» в список и рекурсивно вызываем посетителя для обработки всех подузлов текущей ветви. Это возвращает набор списков, и мы используем 'map_concat', чтобы превратить их в один список, который содержит все пути доступа из текущей ветви.

Теперь вы можете переписать это, чтобы получить список целых чисел: 

let rec visitor2 lst tree = 
  match tree with
  | Branch(n, sub) -> List.collect (visitor2 (lst * 10 + n)) sub
  | Leaf(n) -> [lst * 10 + n]

// For example...  
> visitor2 0 tr;;
val it : int list = [13; 124; 125]

Вместо того, чтобы объединять списки, мы теперь вычисляем число.

2 голосов
/ 12 ноября 2008

По поводу лени - Вы можете сделать это ленивым, используя тип F # "seq" вместо типа "список". Вот пример: 

let rec visitor2 lst tree =
  match tree with
  | Branch(n, sub) -> Seq.map_concat (visitor2 (lst * 10 + n)) sub
  | Leaf(n) ->
      seq { do printfn "--yielding: %d" (lst * 10 + n)
            yield lst * 10 + n };;

"seq" - это выражение последовательности, представляющее ленивый поток значений. Я добавил «printfn» в код, чтобы мы могли отслеживать, как все выполняется: 

> visitor2 0 tr |> Seq.take 2;;
--yielding: 13
--yielding: 124
val it : seq<int> = seq [13; 124]

Вероятно, вы можете использовать что-то вроде Seq.first, чтобы найти первое значение, представляющее результат.

...