Перейти к содержанию

Реализации алгоритмов/Алгоритм Робинсона — Шенстеда

Материал из Викиучебника — открытых книг для открытого мира
defmodule Schensted do

  # выставка в таблицу
  def insert(table, nil), do: table
  def insert([], x), do: [[x]]
  def insert([current | rest], x) do
    {updated, x1} = insert_into_row(current, x)
    [updated | insert(rest, x1)]
  end

  # вставка в строку
  def insert_into_row([], x), do: {[x], nil}
  def insert_into_row([current | rest], x) when current <= x do
    {updated, x1} = insert_into_row(rest, x)
    {[current | updated], x1}
  end
  def insert_into_row([current | rest], x) when current > x do
    {[x | rest], current}
  end

  # формирование таблицы на основе слова Шенстеда (списка)
  def from_word(w), do: Enum.reduce(w, [], fn(x, acc) -> insert(acc, x) end)

  # вывод таблицы на печать
  def print_table(table), do: IO.inspect(table |> Enum.map (&List.to_tuple/1))

  # примеры
  def example do
    table = [[2, 3, 3, 4],
             [3, 4, 5],
             [6, 7, 8],
             [7, 9]]
    x = 3
    res = insert(table, x)
    print_table res
  end

  def example2, do: [3,1, 2] |> from_word |> print_table

end