scala - Scala 中的组合数学 : How to iterate/enumerate all possibilities to merge multiple sequences/lists (riffle shuffle permutations)

Question

更新的问题:

在我原来的问题中，我不知道如何引用以下问题。为了澄清我的问题，我添加了 following illustration from Wikipedia :

原来这个问题也是以此类比命名的:Riffle shuffle permutations 。基于这个术语，我的问题就变成了:在多副牌的一般情况下，如何迭代/枚举所有 Riffle Shuffle 排列？

原始问题:

假设我们有多个序列，并且我们希望将这些序列合并为一个序列。生成的序列应保留原始序列的顺序。考虑通过从任意(随机)中随机抽取一张卡片，将多叠卡片(例如 Seq[Seq[T]])合并为一个单叠(Seq[T]) ) 堆。所有输入堆栈应完全合并到结果堆栈中。我怎样才能迭代或枚举这样一个结果序列的所有可能的组合？

澄清一下:如果我有三个堆栈 A、B、C(每个堆栈有 5 个元素)，那么我不仅想要这些堆栈的六种可能的排列，例如“所有 A、所有 B、所有 C”和“所有A，所有C，所有B”等。我宁愿想要所有可能的组合，例如“1. of A，1. of B，2. of A，1. of C，3. of A，2 . B，...”。

由于我今天有点不舒服，我的第一个方法非常丑陋，而且还会产生重复:

def enumerateCompositions[T](stacks: Seq[Seq[T]], prefix: Seq[T]): Seq[Seq[T]] = {
  if (stacks.length == 0) return {
    Seq(prefix)
  }
  stacks.zipWithIndex.flatMap{ case (stack, stackInd) =>
    if (stack.length > 0) {
      val stacksWithHeadRemoved = stacks.indices.map{ i =>
        if (i != stackInd) stacks(i) else stacks(i).drop(1)
      }
      enumerateCompositions(stacksWithHeadRemoved, prefix :+ stack.head)
    } else {
      val remainingStacks = stacks.indices.filterNot(_ == stackInd).map(i => stacks(i))
      enumerateCompositions(remainingStacks, prefix)
    }
  }
}

知道如何使其更加优雅并消除重复项吗？

Answer 1

我们将此操作称为“步枪”。这是一个干净的 idomatic 解决方案:

def allRiffles[T](stack1: List[T], stack2: List[T]): List[List[T]] =
  (stack1, stack2) match {
    case (x :: xs, y :: ys) => {
      allRiffles(xs, stack2).map(x :: _) ++
      allRiffles(stack1, ys).map(y :: _)
    }
    case _ => List(stack1 ++ stack2) // at least one is empty
  }

def allRifflesSeq[T](stacks: Seq[List[T]]): List[List[T]] =
  stacks.foldLeft(List(List[T]())) { (z, x) => 
    z.flatMap(y => allRiffles(y, x))
  }

allRiffles 将产生两个堆栈的所有可能的 riffling。 allRifflesSeq 将采用一系列堆栈并使用折叠生成所有可能的 riffling。例如，如果给定栈 A、B 和 C，则它首先生成 A 和 B 的所有可能的 riffling，然后将 C riffles 到每个 riffling 中。

请注意，allRiffles 消耗的堆栈空间与最短堆栈的长度成正比，而 allRifflesSeq 消耗的堆栈空间受最长堆栈长度的限制。此外，返回的列表可能很大(组合爆炸)并消耗大量堆空间。基于 Iterator 的解决方案更安全，但不太美观:

def allRiffles[T](stacks: List[List[T]]): Iterator[List[T]] = new Iterator[List[T]] {
  type Frame = (List[List[T]], List[List[T]], List[T])
  var stack = List[Frame]((Nil, stacks, Nil))

  var ready = false
  var cachedHasNext: Boolean = _
  var cachedNext: List[T] = _

  def computeNext: Unit = {
    while (stack.nonEmpty) {
      val (doneStacks, stacks, prefix) :: stackTail = stack
      stack = stackTail
      stacks match {
        case Nil => {
          cachedNext = prefix.reverse
          cachedHasNext = true
          return
        }
        case Nil :: rest =>
          stack ::= (doneStacks, rest, prefix)
        case (xs@(x :: xtail)) :: rest =>
          if (rest.nonEmpty)
            stack ::= (xs :: doneStacks, rest, prefix)
          val newStacks = doneStacks.reverse ++ (if (xtail.isEmpty) rest
                                                   else xtail :: rest)
          stack ::= (Nil, newStacks, x :: prefix)

      }
    }
    cachedHasNext = false
  }

  def ensureReady = {
    if (!ready) {
      computeNext
      ready = true
    }
  }

  def next = {
    ensureReady
    if (cachedHasNext) {
      val next = cachedNext
      ready = false
      next
    } else Iterator.empty.next
  }

  def hasNext = {
    ensureReady
    cachedHasNext
  }
}