Самостоятельная комбинационная функция в Scala - PullRequest
Новая
       23

Самостоятельная комбинационная функция в Scala

0 голосов
/ 31 мая 2018

Я хочу реализовать комбинированную функцию в Scala, и мой код выглядит следующим образом: 

def combination[A](n: Int, ls: List[A]): List[List[A]] ={
    (n, ls) match{
        case (_, Nil) => List(Nil)
        case (1, _) => ls.map(List(_))
        case (_, _) if n > ls.size => List.empty
        case _ => ls.flatMap(x => combination(n - 1, subList(x, ls)).map(x :: _))
      }
  }
def subList[A](e: A, in: List[A]) = in.takeRight(in.size - in.indexOf(e) - 1)

, но результат не тот, который я ожидаю.Когда я звоню combination(3, List('a, 'b, 'c, 'd, 'e, 'f).это даст мне эти результаты с одним или двумя элементами, такими как List ('d,' f), List ('f) и так далее.Может кто-нибудь помочь мне найти проблему?Спасибо.

Обновление : правильная версия 

def combination[A](n: Int, ls: List[A]): List[List[A]] ={
    (n, ls) match{
        case (_, Nil) => Nil
        case (1, _) => ls.map(List(_))
        case (_, _) if n > ls.size => Nil
        case _ => ls.flatMap(x => combination(n - 1, subList(x, ls)).map(x :: _))
      }
  }
def subList[A](e: A, in: List[A]) = in.takeRight(in.size - in.indexOf(e) - 1)

Ответы [ 3 ]

0 голосов
/ 31 мая 2018

Слишком много случаев, ненужные сложные combinations2 и subList.

Вспомните, как определены комбинации .Если у вас есть набор {a1, ..., aN}, и вы хотите выбрать k элементы из этого набора, то вы можете по существу просто две вещи:

  • Вы не делаетевключите a1 в подмножество.Затем вы должны выбрать k элементов из оставшихся {a2, ..., aN}.
  • Вы включаете a1 в подмножество.Затем вы должны выбрать k-1 элементы из {a2, ..., aN} и добавить a0 к этим k-1 элементам.

Вот откуда взята формула 

C(N, k) =         C(N - 1, k) + C(N - 1, k - 1)

.

В коде это просто: 

def comb[A](ls: List[A], k: Int): List[List[A]] = {
  if (k == 0) List(Nil)
  else ls match {
    case Nil => List()
    case h :: t => comb(t, k) ++ comb(t, k - 1).map(h :: _)
  }
}

Пример: 

comb(List('a, 'b, 'c, 'd, 'e), 3) foreach println

дает: 

List('c, 'd, 'e)
List('b, 'd, 'e)
List('b, 'c, 'e)
List('b, 'c, 'd)
List('a, 'd, 'e)
List('a, 'c, 'e)
List('a, 'c, 'd)
List('a, 'b, 'e)
List('a, 'b, 'd)
List('a, 'b, 'c)
0 голосов
/ 31 мая 2018

Существует гораздо более простой способ сделать это 

def comb[A](n: Int, ls:List[A]): List[List[A]] = {
  if(ls.isEmpty) List(Nil)
  else ls.toSet[A].subsets.map(_.toList).filter(_.length == n).toList
}

Scala fiddle

0 голосов
/ 31 мая 2018

В последнем случае вы звоните combination2.Если вы измените на combination (с разумным определением subList), это сработает.Я думаю, что это что-то от промежуточной версии.

...