Функция Scala для получения всех отсортированных подмножеств размера k

Question

Мне дан набор размера L и я хочу создать каждое отсортированное подмножество размера k.Было бы здорово, если бы ваше решение было в scala, но, возможно, я смогу перевести сам.

Пример выполнения для L = 6 и k = 3 должен дать.

1, 2, 3
1, 2, 4
1, 2, 5
1, 2, 6
1, 3, 4
1, 3, 5
1, 3, 6
1, 4, 5
1, 4, 6
1, 5, 6
2, 3, 4
2, 3, 5
2, 3, 6
2, 4, 5
2, 4, 6
2, 5, 6
3, 4, 5
3, 4, 6
3, 5, 6
4, 5, 6

Моя попытка scala была что-то вроде:

object Util {
  def main(args : Array[String]) : Unit = {
    starts(6,3,1)
  }

  def starts(L: Int, num: Int, level: Int) : List[List[Int]] = {
    if( num == 0 ) {
      return List()
    }else{
      (level to (L-num+1)).map( o => o :: starts(L,num-1,level+1))
    }
  }
}

Я надеюсь, вы можете помочь мне.

Answer 1

Все, что вам нужно, это

def subsets(L: Int, k: Int) =  
  1 to L combinations k

Результаты:

scala> subsets(6, 3) foreach println
Vector(1, 2, 3)
Vector(1, 2, 4)
Vector(1, 2, 5)
Vector(1, 2, 6)
Vector(1, 3, 4)
Vector(1, 3, 5)
Vector(1, 3, 6)
Vector(1, 4, 5)
Vector(1, 4, 6)
Vector(1, 5, 6)
Vector(2, 3, 4)
Vector(2, 3, 5)
Vector(2, 3, 6)
Vector(2, 4, 5)
Vector(2, 4, 6)
Vector(2, 5, 6)
Vector(3, 4, 5)
Vector(3, 4, 6)
Vector(3, 5, 6)
Vector(4, 5, 6)

по мере необходимости.

Answer 2

Если у вас на самом деле блоков , а не записей , то вам нужно знать, какова длина каждого блока. То, что вы показали, относится к записям (или, что то же самое, к блокам длиной 1).

Во-первых, обратите внимание, что у нас должно быть L>=k. Во-вторых, обратите внимание, что если первая запись - i, остальные возможности - i+f(L-i,k-1), где f - это то, что создает записи, и предполагается, что + распределяется по коллекциям. Наконец, отметим, что flatMap с функцией, которая создает последовательности для каждого элемента, распакует результат в одну последовательность.

Теперь, когда у нас есть все, что нам нужно знать:

def choices(N: Int, k: Int): List[List[Int]] = {
  if (k==1) (1 to N).toList.map(x => List(x))
  else if (N < k) Nil
  else (1 to 1+N-k).toList.flatMap{ i =>
    choices(N-i,k-1).map(xs => i :: xs.map(_ + i))
  }
}

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

def blockchoices(N: Int, k: Int, size: Int): List[List[Int]] = {
  if (k==1) (1 to N+1-size).toList.map(x => List(x))
  else if (N <= k+size) Nil
  else (1 to 2+N-k-size).toList.flatMap{ i =>
    choices(N-i+1-size, k-1, size).map(xs => i :: xs.map(_ + i+size-1))
  }
}

(указана начальная запись блока).

Answer 3

Вы можете начать с этого

def subsets(start: Int, end: Int, count: Int) :Seq[Seq[Int]] = (
  if (count == 0) 
    List(Nil)
  else 
    for(head <- start to end; tail <- subsets(head + 1, end, count -1)) 
    yield head +: tail
)