使用线性供应流中的值填充嵌套结构

问题描述 投票：2回答：3

我陷入了解决下一个问题的困境：

想象一下，我们有一个数组结构，任何结构，但是对于这个例子，让我们使用：

[
    [ [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] 
]

有什么建议？我只是硬编码给定结构的位置。但这不是动态的。

algorithm data-structures functional-programming stream nested
3个回答
2
投票

这是Scala中的草图。无论您的语言是什么，您首先必须以某种方式表示树状数据结构：

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部分将另一个嵌套数组作为参数，并将平面数组重新整形为嵌套数组的形状。扁平化非常简单：

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-tree的样子：

[
  [
    [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的不太遥远的后代进行某些函数式编程的人来说，或多或少都应该理解。

4
投票

只需递归结构，然后使用迭代器按顺序生成值：

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));
2
投票

几个月前你的问题变成了I've already answered，无论如何都是一个非常相似的问题。

那里的代码需要稍微调整一下，以使它适合这里。在Scheme中：

(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

第一个参数是值的线性列表，第二个参数是要重新创建其结构的嵌套列表。确保线性值列表中有足够的元素在您身上。

我们称之为

> (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写的 - continuation-passing风格：

我们处理嵌套结构的一部分，同时用线性电源的值代替叶子;然后我们用剩余的供应来处理剩余的结构;然后我们将处理这两个子部分得到的两个结果合并起来。对于类似LISP的嵌套列表，它通常是“car”和“cdr”单元格的“cons”，即树的顶部节点。

这正是Bergi的代码正在做的事情，基本上是功能性的。

在一个虚构的模式匹配伪代码中，它可能更容易阅读/跟随

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 monad所关注的;使用Haskell的do表示法，上面将写成

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)一样，但是明确如此。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.