генерировать все возможности при обмене элементами между двумя списками в Scala - PullRequest
Новая
       40

генерировать все возможности при обмене элементами между двумя списками в Scala

0 голосов
/ 01 июня 2018

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

val a = List(1,2,3)
val b = List(4,5,6)
...
//result
List(
    (List(1,2,3), List(4,5,6)),
    (List(1,2,6), List(4,5,3)),
    (List(1,5,3), List(4,2,6)),
    (List(1,5,6), List(4,2,3)),
    (List(4,2,3), List(1,5,6)),
    (List(4,2,6), List(1,5,3)),
    (List(4,5,3), List(1,2,6)),
    (List(4,5,6), List(1,2,3))
)

Я мог бы сделать это с помощью циклов, но я хочу использовать неизменяемые списки и не понимаю, как это сделать с помощью функции генератора (yield).Есть идеи?

Ответы [ 2 ]

0 голосов
/ 01 июня 2018

Это функционально дружественный подход к программированию: 

def combine[T](xx: List[T], yy: List[T]): List[(List[T], List[T])] = (xx, yy) match {
  case (Nil, Nil) => Nil
  case (x :: Nil, y :: Nil) => List(
    (List(x), List(y)),
    (List(y), List(x))
  )
  case (x :: xs, y :: ys) =>
    val results = combine(xs, ys)
    results.map { case (rx, ry) => (x :: rx, y :: ry) } ++
      results.map { case (rx, ry) => (y :: rx, x :: ry)}
  case _ =>
    sys.error("Input of non-matching sizes")
}

К сожалению, это не хвостовая рекурсия.

Но это работает: 

val r = combine(List(1, 2, 3), List(4, 5, 6))
r.foreach(println)

Вывод: 

(List(1, 2, 3),List(4, 5, 6))
(List(1, 2, 6),List(4, 5, 3))
(List(1, 5, 3),List(4, 2, 6))
(List(1, 5, 6),List(4, 2, 3))
(List(4, 2, 3),List(1, 5, 6))
(List(4, 2, 6),List(1, 5, 3))
(List(4, 5, 3),List(1, 2, 6))
(List(4, 5, 6),List(1, 2, 3))
0 голосов
/ 01 июня 2018

Возможное решение может быть комбинацией .subsets и .updated: 

scala> Set(0,1,2).subsets
Set()
Set(0)
Set(1)
Set(2)
Set(0, 1)
Set(0, 2)
Set(1, 2)
Set(0, 1, 2)

scala> (a.updated(0,b(0)), b.updated(0,a(0)))
(List(4, 2, 3),List(1, 5, 6))

Следовательно: 

scala> (0 to a.length - 1).toSet.subsets
  .map(_.foldLeft((a,b)){ 
    case (acc, i) => (acc._1.updated(i,b(i)), acc._2.updated(i,a(i)))})
(List(1, 2, 3),List(4, 5, 6))
(List(4, 2, 3),List(1, 5, 6))
(List(1, 5, 3),List(4, 2, 6))
(List(1, 2, 6),List(4, 5, 3))
(List(4, 5, 3),List(1, 2, 6))
(List(4, 2, 6),List(1, 5, 3))
(List(1, 5, 6),List(4, 2, 3))
(List(4, 5, 6),List(1, 2, 3))
  1. После генерации subsetsпоменять местами индексы
  2. Мы можем fold использовать в качестве нуля / заполнить кортеж со списками ввода
  3. При каждом индексе из Set мы непременно поменяем местами элементы обоих списков a(i)<->b(i)

Это чисто, но не эффективно для длинных списков.

...