列出给定模型铁路上可能的火车路线

Question

我想计算给定模型铁路上的可用路线。

假设：

所有火车仅在称为火车站的定义点开始和停止。
火车在旅途中不会相撞。不用担心。
我们不必考虑火车的长度。我们假设它是一个火车头，它需要一个原子的space。
一个火车站只能停一列火车。
火车可以在同一个火车站起停。

所有火车的起始位置和结束位置都存储在地图中。所有排列都存储在一个列表中。示例：

iex(1)> Trains.list_routes(["ICE"], ["Hamburg", "Frankfurt"])
[
  %{end: %{"ICE" => "Hamburg"}, start: %{"ICE" => "Hamburg"}},
  %{end: %{"ICE" => "Frankfurt"}, start: %{"ICE" => "Frankfurt"}},
  %{end: %{"ICE" => "Frankfurt"}, start: %{"ICE" => "Hamburg"}},
  %{end: %{"ICE" => "Hamburg"}, start: %{"ICE" => "Frankfurt"}}
]

铁路模型可能如下所示（红色数字表示火车站）：

对于该模型铁路上的两列火车，函数将以这种方式调用：

Trains.list_routes([:red_train, :blue_train], ["1", "2", "3", "4", "5"])

这是我当前的代码：

defmodule Trains do
  @moduledoc """
  Documentation for `Trains`.
  """

  @doc """
  Returns a list of all possible routes.

  ## Examples

      iex> Trains.list_routes([:red_train, :blue_train], ["Station 1", "Station 2"])
      [
        %{
          end: %{blue_train: "Station 2", red_train: "Station 1"},
          start: %{blue_train: "Station 2", red_train: "Station 1"}
        },
        %{
          end: %{blue_train: "Station 1", red_train: "Station 2"},
          start: %{blue_train: "Station 1", red_train: "Station 2"}
        },
        %{
          end: %{blue_train: "Station 1", red_train: "Station 2"},
          start: %{blue_train: "Station 2", red_train: "Station 1"}
        },
        %{
          end: %{blue_train: "Station 2", red_train: "Station 1"},
          start: %{blue_train: "Station 1", red_train: "Station 2"}
        }
      ]
  """
  def list_routes([], []) do
    []
  end

  def list_routes([train], [station]) do
    [
      %{start: %{train => station}, end: %{train => station}}
    ]
  end

  def list_routes([train], [station1, station2]) do
    [
      %{start: %{train => station1}, end: %{train => station1}},
      %{start: %{train => station2}, end: %{train => station2}},
      %{start: %{train => station1}, end: %{train => station2}},
      %{start: %{train => station2}, end: %{train => station1}}
    ]
  end

  def list_routes([train1, train2], [station1, station2]) do
    [
      %{
        start: %{train1 => station1, train2 => station2},
        end: %{train1 => station1, train2 => station2}
      },
      %{
        start: %{train1 => station2, train2 => station1},
        end: %{train1 => station2, train2 => station1}
      },
      %{
        start: %{train1 => station1, train2 => station2},
        end: %{train1 => station2, train2 => station1}
      },
      %{
        start: %{train1 => station2, train2 => station1},
        end: %{train1 => station1, train2 => station2}
      }
    ]
  end

  def list_routes(trains, train_stations) do
    # ???
  end
end

当trains的个数和train_stations的个数都大于1时，如何遍历list_routes(trains, train_stations)的所有组合？

Answer 1

根据您发布的代码，不清楚为什么一列火车允许相同的起点和终点站 %{start: %{train => station1}, end: %{train => station1}} 但两列火车不允许。

良好的开端应该是这样的：

iex|1 ▶ {trains, stations} =
  {~w|red_train blue_train|a, ~w|1 2|}  
#⇒ {[:red_train, :blue_train], ["1", "2"]}
iex|2 ▶ (for t1 <- trains, t2<- trains, t1 != t2,
             s1 <- stations, s2 <- stations,
             do: Enum.sort([{t1, s1}, {t2, s2}])
        ) |> Enum.uniq()
#⇒ [
#   [blue_train: "1", red_train: "1"],
#   [blue_train: "2", red_train: "1"],
#   [blue_train: "1", red_train: "2"],
#   [blue_train: "2", red_train: "2"]
# ]

无论如何，Kernel.SpecialForms.for/1 comprehension is your best friend here. Whether you need combinations and/or permutations, you might want to take a look at my Formulae library, specifically at Formulae.Combinators。

Answer 2

这是问题的解决方案。它使用 Formulae.

mix.exs

def deps do
  [{:formulae, "~> 0.8"}]
end

lib/trains.ex

def list_routes([], []) do
  []
end

def list_routes(trains, train_stations)
    when is_list(trains) and
            is_list(train_stations) and 
            length(train_stations) >= length(trains) do
  possible_states =
    Enum.map(Formulae.permutations(train_stations, length(trains)), &Enum.zip(trains, &1))

  for state_start <- possible_states, state_end <- possible_states do
    %{start: state_start, end: state_end}
  end
end

结果：

iex(1)> Trains.list_routes([:red_train, :blue_train], ["Station 1", "Station 2"])
[
  %{
    end: [red_train: "Station 1", blue_train: "Station 2"],
    start: [red_train: "Station 1", blue_train: "Station 2"]
  },
  %{
    end: [red_train: "Station 2", blue_train: "Station 1"],
    start: [red_train: "Station 1", blue_train: "Station 2"]
  },
  %{
    end: [red_train: "Station 1", blue_train: "Station 2"],
    start: [red_train: "Station 2", blue_train: "Station 1"]
  },
  %{
    end: [red_train: "Station 2", blue_train: "Station 1"],
    start: [red_train: "Station 2", blue_train: "Station 1"]
  }
]

列出给定模型铁路上可能的火车路线

List possible train routes on a given model railway

elixir