количество 5-значных чисел без повторяющихся цифр больше 12345

Question

Я новичок в OCaml и алгоритмах.Я пытаюсь получить число из 5-значных чисел без повторяющихся цифр больше 12345.

Вот что я сделал в OCaml, я попытался сделать хвостовую рекурсивную, насколько это возможно, и я также использовал потоки.Но все же из-за размера стек переполнился:

type 'a stream = Eos | StrCons of 'a * (unit -> 'a stream)

let rec numberfrom n= StrCons (n, fun ()-> numberfrom (n+1))

let nats = numberfrom 1

let rec listify st n f=
  match st with
  |Eos ->f []
  |StrCons (m, a) ->if n=1 then f [m] else listify (a ()) (n-1) (fun y -> f (m::y))


let rec filter (test: 'a-> bool) (s: 'a stream) : 'a stream=
  match s with
  |Eos -> Eos
  |StrCons(q,w) -> if test q then StrCons(q, fun ()->filter test (w ()))
      else filter test (w ())



let rec check_dup l=
  match l with
  | [] -> false
  | h::t->
      let x = (List.filter (fun x -> x = h) t) in
      if (x == []) then
        check_dup t
      else
        true;;

let digits2 d =
  let rec dig acc d =
    if d < 10 then d::acc
    else dig ((d mod 10)::acc) (d/10) in
  dig [] d

let size a=
  let rec helper n aa=
    match aa with
    |Eos-> n
    |StrCons (q,w) -> helper (n+1) (w())
  in helper 0 a

let result1 = filter (fun x -> x<99999 && x>=12345 && (not (check_dup (digits2 x)))) nats



(* unterminating : size result1 *)
        (*StackOverflow: listify result1 10000 (fun x->x) *)

Answer 1

Проблема в том, что размер вашего потока result1 не определен.

Действительно, nats - это бесконечный поток: он никогда не возвращает Eos.

Однако фильтрация бесконечного потока приводит к другому бесконечному потоку поскольку отфильтрованный поток возвращает Eos только после того, как базовый поток делает это:

let rec filter (test: 'a-> bool) (s: 'a stream) : 'a stream=
  match s with
  | Eos -> Eos
  | StrCons(q,w) -> if test q then StrCons(q, fun ()->filter test (w ()))
      else filter test (w ())

Следовательно, size result1 застревает, пытаясь достичь конца целых чисел.

Обратите внимание также, что в последней версии стандартной библиотеки ваш тип stream называется Seq.node.

Answer 2

Я не могу воспроизвести вашу проблему.Когда я загружаю ваш код, я вижу это:

# List.length (listify result1 10000 (fun x -> x));;
- : int = 10000
# List.length (listify result1 26831 (fun x -> x));;
- : int = 26831

Возможно, ваша система более ограничена в ресурсах, чем моя.

Позвольте мне просто сказать, что обычный способ кодирования хвостовой рекурсивной функцииэто построить список в обратном порядке, а затем обратить его в конце.Это может выглядеть примерно так:

let listify2 st n =
    let rec ilist accum st k =
        match st with
        | Eos -> List.rev accum
        | StrCons (m, a) ->
            if k = 1 then List.rev (m :: accum)
            else ilist (m :: accum) (a ()) (k - 1)
    in
    if n = 0 then []
    else ilist [] st n

У вас все еще есть проблема, что listify не завершается, если вы запрашиваете больше элементов, чем есть в потоке.Возможно, было бы лучше ввести метод обнаружения конца потока и возврата Eos в этой точке.Например, функция filter может принимать функцию, которая возвращает три возможных значения (элемент должен быть отфильтрован, элемент не должен быть отфильтрован, поток должен завершиться).