Декартово произведение двух списков

Дана карта, где цифра связана с несколькими символами

scala> val conversion = Map("0" -> List("A", "B"), "1" -> List("C", "D"))
conversion: scala.collection.immutable.Map[java.lang.String,List[java.lang.String]] =
  Map(0 -> List(A, B), 1 -> List(C, D))

Я хочу сгенерировать все возможные последовательности символов на основе последовательности цифр. Примеры:

"00" -> List("AA", "AB", "BA", "BB")
"01" -> List("AC", "AD", "BC", "BD")

Я могу сделать это для понимания

scala> val number = "011"
number: java.lang.String = 011

Создайте последовательность возможных символов для каждого индекса

scala> val values = number map { case c => conversion(c.toString) }
values: scala.collection.immutable.IndexedSeq[List[java.lang.String]] =
  Vector(List(A, B), List(C, D), List(C, D))

Сгенерировать все возможные последовательности символов

scala> for {
     | a <- values(0)
     | b <- values(1)
     | c <- values(2)
     | } yield a+b+c
res13: List[java.lang.String] = List(ACC, ACD, ADC, ADD, BCC, BCD, BDC, BDD)

Здесь все становится некрасиво, и это будет работать только для последовательностей из трех цифр. Есть ли способ добиться того же результата для любой длины последовательности?


scala for-comprehension
person Mark Jayxcela    schedule 21.11.2011    source источник
comment
Строго говоря, то, что вы пытаетесь получить, не является декартовым произведением. Если у вас List[T], вы не гарантируете размер, а также список должен быть однородным.   -  person Vlad Patryshev    schedule 27.05.2014

Ответы (3)


arrow_upward
15
arrow_downward

Следующее предложение не использует for-comprehension. Но я не думаю, что это хорошая идея, потому что, как вы заметили, вы будете привязаны к определенной длине вашего декартова произведения.

scala> def cartesianProduct[T](xss: List[List[T]]): List[List[T]] = xss match {
     |   case Nil => List(Nil)
     |   case h :: t => for(xh <- h; xt <- cartesianProduct(t)) yield xh :: xt
     | }
cartesianProduct: [T](xss: List[List[T]])List[List[T]]

scala> val conversion = Map('0' -> List("A", "B"), '1' -> List("C", "D"))
conversion: scala.collection.immutable.Map[Char,List[java.lang.String]] = Map(0 -> List(A, B), 1 -> List(C, D))

scala> cartesianProduct("01".map(conversion).toList)
res9: List[List[java.lang.String]] = List(List(A, C), List(A, D), List(B, C), List(B, D))

Почему не хвостовая рекурсия?

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

person ziggystar    schedule 21.11.2011

arrow_upward
5
arrow_downward

Я мог бы придумать это:

val conversion = Map('0' -> Seq("A", "B"), '1' -> Seq("C", "D"))

def permut(str: Seq[Char]): Seq[String] = str match {
  case Seq()  => Seq.empty
  case Seq(c) => conversion(c)
  case Seq(head, tail @ _*) =>
    val t = permut(tail)
    conversion(head).flatMap(pre => t.map(pre + _))
}

permut("011")
person 0__    schedule 21.11.2011
comment
Спасибо, Sciss, я принял ответ ziggystar, так как он опубликовал его раньше, и оба ответа довольно хороши. Мне особенно нравится ваша идея разложить for на цепочку flatMaps. - person Mark Jayxcela; 22.11.2011
comment
Ответ @Mark Sciss отличается от моего только синтаксически (по крайней мере, в части построения комбинаций). Он использует map и flatMap, а я использую синтаксический сахар для понимания, который транслируется компилятором в код Sciss. Единственное отличие состоит в том, что я извлек метод для декартова произведения. - person ziggystar; 22.11.2011
comment
@ziggystar Отлично, теперь я лучше понимаю, что происходит за кулисами. - person Mark Jayxcela; 23.11.2011

arrow_upward
-1
arrow_downward

Я просто сделал это следующим образом, и это работает

    def cross(a:IndexedSeq[Tree], b:IndexedSeq[Tree]) = {
        a.map (p => b.map( o => (p,o))).flatten
    }

Не вижу тип $Tree, с которым я имею дело, он работает и для произвольных коллекций.

person Vijay Krishna Menon    schedule 27.08.2016