Заполните вложенную структуру значениями из линейного потока поставок

Question

Я застрял в решении следующей задачи:

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

[
    [ [1, 2], [3, 4], [5, 6] ],
    [ 7, 8, 9, 10 ]
]

Для удобства япреобразовать эту структуру в плоский массив, например:

[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

Представьте, что после определенных операций наш массив выглядит следующим образом:

[ 1, 2, 3, 4, 12515, 25125, 12512, 8, 9, 10]

ПРИМЕЧАНИЕ: эти значения являются результатом какой-то операции, япросто хочу указать, что не зависит от структуры или их позиций.

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

[ 
   [ [1, 2], [3, 4] , [12515, 25125] ],
   [ 12512, 8, 9, 10] 
]

Есть предложения?Я просто жестко запрограммировал позиции в данной структуре.Но это не динамично.

Answer 1

Вот эскиз в Скала.Каким бы ни был ваш язык, сначала вы должны как-то представить древовидную структуру данных:

sealed trait NestedArray
case class Leaf(arr: Array[Int]) extends NestedArray {
  override def toString = arr.mkString("[", ",", "]")
}
case class Node(children: Array[NestedArray]) extends NestedArray {
  override def toString = 
    children
      .flatMap(_.toString.split("\n"))
      .map("  " + _)
      .mkString("[\n", "\n", "\n]")
}

object NestedArray {
  def apply(ints: Int*) = Leaf(ints.toArray)
  def apply(cs: NestedArray*) = Node(cs.toArray)
}

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

Теперь вы, по сути, хотите построить кодер-декодер, где часть encode просто сглаживает все, иdecode part принимает в качестве аргумента другой вложенный массив и преобразовывает плоский массив в форму вложенного массива.Выравнивание очень простое:

def encode(a: NestedArray): Array[Int] = a match {
  case Leaf(arr) => arr
  case Node(cs) => cs flatMap encode
}

Восстановление структуры также не так сложно.Я решил отслеживать позицию в массиве, передавая явный int -индекс:

def decode(
  shape: NestedArray, 
  flatArr: Array[Int]
): NestedArray = {
  def recHelper(
    startIdx: Int, 
    subshape: NestedArray
  ): (Int, NestedArray) = subshape match {
    case Leaf(a) => {
      val n = a.size
      val subArray = Array.ofDim[Int](n)
      System.arraycopy(flatArr, startIdx, subArray, 0, n)
      (startIdx + n, Leaf(subArray))
    }
    case Node(cs) => {
      var idx = startIdx
      val childNodes = for (c <- cs) yield {
        val (i, a) = recHelper(idx, c)
        idx = i
        a
      }
      (idx, Node(childNodes))
    }
  }
  recHelper(0, shape)._2
}

Ваш пример:

val original = NestedArray(
  NestedArray(NestedArray(1, 2), NestedArray(3, 4), NestedArray(5, 6)),
  NestedArray(NestedArray(7, 8, 9, 10))
)

println(original)

Вот что этовыглядит как ASCII-дерево:

[
  [
    [1,2]
    [3,4]
    [5,6]
  ]
  [
    [7,8,9,10]
  ]
]

Теперь воссоздайте дерево той же формы из другого массива:

val flatArr = Array(1, 2, 3, 4, 12515, 25125, 12512, 8, 9, 10)
val reconstructed = decode(original, flatArr)

println(reconstructed)

это дает вам:

[
  [
    [1,2]
    [3,4]
    [12515,25125]
  ]
  [
    [12512,8,9,10]
  ]
]

Я надеюсь, что это должно быть более или менее понятно для любого, кто занимается функциональным программированием на не слишком отдаленном потомке ML.

Answer 2

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

Код должен быть немного подправлен, чтобы он подходил здесь.На схеме:

(define (merge-tree-fringe vals tree k)
  (cond
    [(null? tree)
     (k vals '())]
    [(not (pair? tree))                  ; for each leaf:
     (k (cdr vals) (car vals))]          ;   USE the first of vals
    [else
     (merge-tree-fringe vals (car tree) (lambda (Avals r)      ; collect 'r' from car,
      (merge-tree-fringe Avals (cdr tree) (lambda (Dvals q)    ;  collect 'q' from cdr,
       (k Dvals (cons r q))))))]))       ; return the last vals and the combined results

Первый аргумент - это линейный список значений, второй - вложенный список, структура которого должна быть воссоздана.Убедитесь, что в линейном списке значений достаточно элементов: на вас *1009*.

Мы называем это

> (merge-tree-fringe '(1 2 3 4 5 6 7 8) '(a ((b) c) d) (lambda (vs r) (list r vs)))
'((1 ((2) 3) 4) (5 6 7 8))

> (merge-tree-fringe '(1 2 3 4 5 6 7 8) '(a ((b) c) d) (lambda (vs r) r))
'(1 ((2) 3) 4)

В связанном ответе есть словоблудие с объяснениями того, что происходит.Короче говоря, он написан в CPS - в стиле продолжения :

Мы обрабатываем часть вложенной структуры, подставляя листья значениями из линейногопоставка;затем мы обрабатываем остальную часть конструкции с оставшимся запасом;затем мы объединяем два результата, полученные при обработке двух частей.Для LISP-подобных вложенных списков обычно это "car" и "cdr" ячейки "cons", то есть верхний узел дерева.

Это делает то, что делает код Берги, по существу, но в функциональном стиле.

---

В воображаемом псевдокоде, соответствующем шаблону, который может быть легче читать / отслеживать, онis

merge-tree-fringe vals tree = g vals tree (vs r => r)
    where
    g vals [a, ...d] k = g vals a (avals r =>    -- avals: vals remaining after 'a'
                             g avals d (dvals q =>    -- dvals: remaining after 'd'
                                 k dvals [r, ...q] ))     -- combine the results
    g vals        [] k = k vals []                           -- empty 
    g [v, ...vs]  _  k = k vs   v                            -- leaf: replace it

Эта вычислительная схема потоковой передачи изменяющегося состояния посредством вычислений - это как раз то, о чем монада State;с пометкой do на Haskell вышеприведенное будет записано как

merge_tree_fringe vals tree = evalState (g tree) vals
    where
    g [a, ...d] = do { r <- g a ; q <- g d ; return [r, ...q] }  
    g        [] = do { return [] }           
    g        _  = do { [v, ...vs] <- get ; put vs ; return v }  -- leaf: replace

put и get работают с состоянием, которым манипулируют, обновляют и передают неявно;vals - начальное состояние;окончательное состояние незаметно отбрасывается evalState, как и наше (vs r => r) выше, но явно так.

Answer 3

Просто пройдитесь по структуре и используйте итератор для генерации значений в следующем порядке:

function fillWithStream(structure, iterator) {
    for (var i=0; i<structure.length; i++)
        if (Array.isArray(structure[i]))
            fillWithStream(structure[i], iterator);
        else
            structure[i] = getNext(iterator);
}
function getNext(iterator) {
    const res = iterator.next();
    if (res.done) throw new Error("not enough elements in the iterator");
    return res.value;
}

var structure = [
    [ [1, 2], [3, 4], [5, 6] ],
    [ 7, 8, 9, 10 ]
];
var seq = [1, 2, 3, 4, 12515, 25125, 12512, 8, 9, 10];
fillWithStream(structure, seq[Symbol.iterator]())
console.log(JSON.stringify(structure));