Как получить комбинации из n предметов из списка предметов в Scala? - PullRequest
Новая
       40

Как получить комбинации из n предметов из списка предметов в Scala?

1 голос
/ 27 апреля 2020

Мне нужно сгенерировать все комбинации размера n из списка предметов. Я пытаюсь решить это функционально с помощью рекурсии. Вот мое решение: 

  def combinations(i: Int, value: List[Symbol]): List[List[Symbol]] = {
    if (i == 0) List(Nil)
    else if (i == value.size) List(value)
    else value match {
      case Nil => List(Nil)
      case head::tail => {
        combinations(i, tail) ::: combinations(i - 1, tail) map { tailCombos => head :: tailCombos }
      }
    }
  }

Вот мой тестовый ввод: combinations(3, List('a, 'b, 'c, 'd ))

Я получаю List(List('a, 'b, 'c, 'd), List('a, 'b, 'c, 'd), List('a, 'b, 'c, 'd), List('a, 'b, 'c))

вместо List(List('b, 'c, 'd), List('a, 'b, 'd), List('a, 'c, 'd), List('a, 'b, 'c))

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

1 Ответ

1 голос
/ 27 апреля 2020

Это не более, чем какая-то синтактическая c путаница. Синтаксис, основанный на пробелах (для него есть название, но я забыл), был введен в первые дни и не вызывал ничего, кроме путаницы. Я настоятельно рекомендую придерживаться синтаксиса точки.

Что происходит из-за оценки слева направо, карта применяется ко всему результату combinations(i, tail) ::: combinations(i - 1, tail)

вместо этого, если вы сделали 

 combinations(i, tail) ::: combinations(i - 1, tail).map{ tailCombos => head :: tailCombos }

Вы получит желаемый результат.

Рабочий scast ie -> https://scastie.scala-lang.org/dV3BJ9fIQBSckt1LLTfbrw

PS Если вы используете кошек, вы можете положиться на встроенный комбайн на полугруппах, чтобы сгенерировать это также

...