1

ここに1つのインタビューの質問があります：

与えられた数の同じ桁で形成できる次に大きい数を見つけます。

入力：4765、出力：5467

を使用する場合array、それはそれほど難しいことではありません。

  1. 数値を桁配列に変換します。
  2. x配列をスキャンし、次の隣人が大きい最新の（最も低い位置）桁（たとえば）を記録します
  3. 次のネイバーが小さい場合（つまり、降順である場合）、xよりも大きい最小の桁を記録します（たとえば、y）
  4. 最後に、xとyを交換します

しかし、OCamlでは、を使用するlistと、その方法がわかりません。アルゴリズムが再帰を難しくしているようです。

助言がありますか？

編集：

機能的な方法を希望していることに注意してください（リストを使用）

編集

@comingstormのアドバイスに従うことで、私は次のように実装しました。

exception NotFound;;


let rev_list_of_int n = 
  let rec process n = 
    let x = n / 10 and y = n mod 10 
    in 
    if x = 0 && y = 0 then []
    else 
      y::(process x)
  in 
  process n;;

let find_next_by_list n =
  let l = rev_list_of_int n
  in
  let rec find_x before_x x after_x = 
    match after_x with
    | [] | _::[] -> (before_x, -1, after_x)
    | hd1::hd2::tl -> 
      if hd1 > hd2 then (hd1::before_x, hd2, tl)
      else find_x (hd1::before_x) x (hd2::tl)
  in 
  let (bx, x, ax) = find_x [] (-1) l (* ax is rev *)
  in 
  if x = -1 then raise NotFound
  else 
    let rec find_y x path = function
    | [] -> raise NotFound
    | hd::tl -> 
      if hd > x then (path, hd, tl)
      else find_y x (hd::path) tl
    in 
    let (left, y, right) = find_y x [] (List.rev bx) (* left is rev, right is not  *)
    in 
    (* rev ax, then y, then right, then x, then rev left*)
    (List.rev_append (y::ax) right) @ (x::List.rev left)
4

3 に答える 3

2

これを機能的に実装するには、数字のリストを逆の順序で維持する方が効率的です。これにより、最も急速に変化する数字がリストの先頭に近くなります。これにより、実装はリスト全体の再割り当てを回避し、償却パフォーマンスを向上させることができます。

digits（最も重要でないものから最も重要なものへ）の逆のリストが与えられた場合：

Starting at the least-significant digit (the head of the reversed list):
  look for the first digit smaller than its predecessor:  call it "a_k"
  save the list of digits after a_k as:  "unchanged"
Starting again at the least-significant digit:
  look for the first digit larger than a_k:  call it "a_l"
Accumulate the output list functional-style, starting with "unchanged":
  add a_l to the head of the list
  starting a third time at the least-significant digit:
    add each digit to the head of the output (reversing that portion of the list)
      stopping before a_l
    add a_k to the head of the output, instead of a_l
    after skipping a_l, continue to add digits from original to output
      stopping before a_k

つまり、機能的なスタイルで行うには、リストの「変更された」スワップ/リバース部分を適切に構築する必要があります。リストを最下位桁の最初の順序で維持する必要はありませんが（上記の擬似コードで想定されているように）、そうすると、next_permutation関数は時間内にO（1）のパフォーマンスを償却し、メモリを割り当てます。

[編集：訂正、O（1）のパフォーマンスは、すべての桁が異なる場合のみです...]

数字を最上位桁の最初の順序で維持したい場合でも、同等のスキャンとスワップ/リバース領域の再構築を実行してから、変更されていない領域の順序どおりのコピーを実行する必要があります。

于 2013-03-25T18:29:48.247 に答える
1

辞書式順序で次の順列を生成するだけです。

Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
Swap a[k] with a[l].
Reverse the sequence from a[k + 1] up to and including the final element a[n].

ウィキペディアで見つかりました。OCamlの実装はここにあります：

The following Ocaml code implements a variation on this algorithm (it returns the permutations of 1..n in reverse reverse-lexicographic order) :

(* exchange into l @ [x] @ accu x with the last element of l which is > x *)
let rec swap l x accu = match l with
| a::b::t when b > x -> a :: (swap (b::t) x accu)
| a::t -> (x::t) @ (a::accu)
| _ -> failwith "this can't happen"
;;

(* permut l m accu computes the permutation p' following p = rev(l)@m,
stores it into accu and recalls itself until p has no successor *)
let rec permut l m accu = match l,m with
| a::_, b::t when a > b -> let p = swap l b t in permut [] p (p::accu)
| _, b::t -> permut (b::l) t accu
| _, [] -> accu
;;
于 2013-03-25T17:24:31.833 に答える
0

Kwarizが（本質的に）指摘しているように、リストで同じソリューションを使用できます。配列ソリューションは一定時間で数字を交換できますが、最初にすべてをスキャンするには線形時間がかかります。数字のリストを使用すると、線形スキャンに加えて、数字を交換する線形操作が可能になります。

よりきれいな再帰的解決策を思い付くことが可能かもしれません。問題は、リストのかなり「グローバルな」プロパティを使用していることです。それを通常の再帰的な部分に分割するのは簡単ではありません。しかし、それほど遠くはありません。1つには、リストの末尾で操作を実行できる場合、これはリスト全体の正しい結果でもあります（ヘッドが追加されています）。

于 2013-03-25T18:09:22.240 に答える