Список комбинаций С повторениями в Scala

В одном из ответов вопрос был перефразирован - надеюсь, сам вопрос тоже будет отредактирован. Кто-то другой ответил на правильный вопрос. Я оставлю этот код ниже на тот случай, если кто-то сочтет его полезным.

Это решение действительно сбивает с толку. «Комбинация» без повторов называется перестановкой. Это может выглядеть так:

def perm[T](n: Int, l: List[T]): List[List[T]] =
  n match {
    case 0 => List(List())
    case _ => for(el <- l;
                  sl <- perm(n-1, l filter (_ != el)))
              yield el :: sl
  }

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

def perm[T](n: Int, l: List[T]): List[List[T]] = {
  def perm1[T](n: Int, l: List[T]): List[List[T]] =
    n match {
      case 0 => List(List())
      case _ => for(el <- l;
                    (hd, tl) = l span (_ != el);
                    sl <- perm(n-1, hd ::: tl.tail))
                yield el :: sl
    }
  perm1(n, l).removeDuplicates
}

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

Например, если мы берем List (1,2,3 ), мы ' Я буду составлять списки, образованные 1 и perm (List (2,3)), 2 и perm (List (1,3)) и 3 и perm (List (1,2)).

Поскольку мы делаем произвольно- размера перестановок, мы отслеживаем, как долго может быть каждая подстановка. Если размер подстановки равен 0, важно, чтобы мы возвращали список, содержащий пустой список. Обратите внимание, что это не пустой список! Если бы мы вернули Nil в случае 0, в вызывающей perm не было бы элемента для sl, и все "for" дало бы Nil. Таким образом, sl будет присвоено значение Nil, и мы составим список el :: Nil, в результате чего получится List (el).

Я думал об исходной проблеме, и я опубликую здесь свое решение для справки. . Если вы имели в виду отсутствие повторяющихся элементов в ответе в результате дублирования элементов во входных данных, просто добавьте removeDuplicates, как показано ниже.

def comb[T](n: Int, l: List[T]): List[List[T]] =
n match {
  case 0 => List(List())
  case _ => for(i <- (0 to (l.size - n)).toList;
                l1 = l.drop(i);
                sl <- comb(n-1, l1.tail))
            yield l1.head :: sl
}

Я знаю, это немного уродливо. Мне нужно использовать toList для преобразования диапазона (возвращаемого «to») в список, чтобы само «for» возвращало список. Я мог бы покончить с «l1», но я думаю, это проясняет то, что я делаю. Поскольку здесь нет фильтра, изменить его для удаления дубликатов намного проще:

def comb[T](n: Int, l: List[T]): List[List[T]] = {
  def comb1[T](n: Int, l: List[T]): List[List[T]] =
    n match {
      case 0 => List(List())
      case _ => for(i <- (0 to (l.size - n)).toList;
                    l1 = l.drop(i);
                    sl <- comb(n-1, l1.tail))
                yield l1.head :: sl
    }
  comb1(n, l).removeDuplicates
}

Дэниел - Я не уверен, что Алекс имел в виду под дубликатами, возможно, следующее дает более подходящий ответ:

def perm[T](n: Int, l: List[T]): List[List[T]] =
  n match {
    case 0 => List(List())
    case _ => for(el <- l.removeDuplicates;
                sl <- perm(n-1, l.slice(0, l.findIndexOf {_ == el}) ++ l.slice(1 + l.findIndexOf {_ == el}, l.size)))
            yield el :: sl
}

Запуск от имени

perm(2, List(1,2,2,2,1)) 

дает:

List(List(2, 2), List(2, 1), List(1, 2), List(1, 1))

в отличие от:

List(
  List(1, 2), List(1, 2), List(1, 2), List(2, 1), 
  List(2, 1), List(2, 1), List(2, 1), List(2, 1), 
  List(2, 1), List(1, 2), List(1, 2), List(1, 2)
)

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

Я написал аналогичное решение проблемы в своем блоге: http: //gabrielsw.blogspot .com / 2009/05 / my-take-on-99-issues-in-scala-23-to.html

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

чтобы получить комбинации размера n, возьмите одну элемент набора и добавить его ко всем комбинациям наборов размера n-1 оставшихся элементов, Вот что делает код

 //P26
 def combinations[A](n:Int, xs:List[A]):List[List[A]]={
    def lift[A](xs:List[A]):List[List[A]]=xs.foldLeft(List[List[A]]())((ys,y)=>(List(y)::ys))

    (n,xs) match {
      case (1,ys)=> lift(ys)
      case (i,xs) if (i==xs.size) => xs::Nil
      case (i,ys)=> combinations(i-1,ys.tail).map(zs=>ys.head::zs):::combinations(i,ys.tail)
    }
 }

Как это читать:

Мне пришлось создать вспомогательную функцию, которая «поднимает» список в список списков

Логика находится в операторе соответствия:

Если вы хотите все комбинации размера 1 элементов списка, просто создайте список списков, в котором каждый подсписок содержит элемент исходного (это функция "подъема")

Если комбинации составляют общую длину список, просто верните список, в котором единственным элементом является список элементов (возможна только одна комбинация!)

В противном случае, возьмите начало и конец списка, вычислите все комбинации размера n-1 хвоста (рекурсивный вызов) и добавьте заголовок в каждый из полученных списков (.map (ys.head ::zs)) объединить результат со всеми комбинациями размера n хвоста списка (другой рекурсивный вызов)

Есть ли в этом смысл?