Доступ к индексу определенной ячейки в Scala

Question

Мне нужно написать метод «all()», который возвращает список кортежей; каждый кортеж будет содержать строку, столбец и набор, соответствующие конкретной заданной строке и столбцу, когда функция встречает 0 в списке. Я уже написал функцию «hyp», которая возвращает нужную мне часть, например: Set (1,2). Я использую список списков:

| 0 | 0 | 9 | 
| 0 | x | 0 | 
| 7 | 0 | 8 | 

Если Set (1,2) имеют в виду клетки помечены как х, все() должен возвращать: (1,1, Set (1,2)), где 1,1 - индекс строки и столбца. Я написал этот метод, используя zipWithIndex. Есть ли более простой способ доступа к индексу, как в этом случае без zipWithIndex? Заранее спасибо Код:

def all(): List[(Int, Int, Set[Int])] = 
{ 
    puzzle.list.zipWithIndex flatMap 
    { 
    rowAndIndex => 
    rowAndIndex._1.zipWithIndex.withFilter(_._1 == 0) map 
    { 
     colAndIndex => 
     (rowAndIndex._2, colAndIndex._2, hyp(rowAndIndex._2, colAndIndex._2)) 
    } 
    } 
} 

The (_._ 1 == 0) потому, что функция должна возвращать (Int, Int, Set()) только тогда, когда он находит 0 в сетке

Answer 1

Самый простой способ, которым я могу думать только классический цикл:

for{ x <- list.indices 
    y <- list(0).indices 
    if list(x)(y) == 0 } yield (x, y, hyp(x, y)) 

это предполагает, что ваш второй размер имеет равномерный размер. С помощью этого кода я также рекомендую использовать Array или Vector, если размер вашей сетки больше 100 или около того, потому что list (x) (y) является операцией O (n).

Answer 2

Общепринято использовать zipWithIndex. Может свести к минимуму борьбы с кортежами/пар через шаблон согласование ВАРА в пределах кортежа:

def all(grid: List[List[Int]]): List[(Int, Int, Set[Int])] = 
    grid.zipWithIndex flatMap {case (row, r) => 
    row.zipWithIndex.withFilter(_._1 == 0) map {case (col, c) => (r, c, hyp(r, c))} 
    } 

может быть преобразована в 100% эквивалент-понимания:

def all(grid: List[List[Int]]): List[(Int, Int, Set[Int])] = 
    for {(row, r) <- grid.zipWithIndex; 
     (col, c) <- row.zipWithIndex if (col == 0)} yield (r, c, hyp(r, c))  

Оба выше дает одинаковый скомпилированный код.

Обратите внимание, что ваше требование означает, что все решения минимальны. O (n) = O (r * c) - вы должны посетить каждую ячейку. Однако общее поведение ответа пользователя60561 равно O (n^2) = O ((r * c)^2): для каждой ячейки в списке (x) (y) находится O (n):

for{ x <- list.indices 
    y <- list(0).indices 
    if list(x)(y) == 0 } yield (x, y, hyp(x, y)) 

Вот аналогичный (императивный!) логика, но O (п):

var r, c = -1 
for{ row <- list; col <- row if col == 0} yield { 
    r += 1 
    c += 1 
    (r, c, hyp(r, c)) 
} 

Рекурсивная версия (использует результаты-аккумулятор для того, чтобы хвостовой рекурсии):

type Grid = List[List[Int]] 
type GridHyp = List[(Int, Int, Set[Int])] 

def all(grid: Grid): GridHyp = { 
    def rowHypIter(row: List[Int], r: Int, c: Int, accum: GridHyp) = row match { 
    case Nil => accum 
    case col :: othCols => rowHypIter(othCols, r, c + 1, hyp(r, c) :: accum)} 
    def gridHypIter(grid: Grid, r: Int, accum: GridHyp) = grid match { 
    case Nil => accum 
    case row :: othRows => gridHypIter(othRows, r + 1, rowHyp(row, r, 0, accum))} 
    gridHypIter(grid, 0, Nil) 
} 

логики 'монадической' (flatmap/map/withFilter или эквивалентные для понимания) часто/обычно опрят, чем рекурсия + сопоставление образцов - очевидно здесь.