recursion - Combinatorics in Scala: How to iterate/enumerate all possibilities to merge multiple sequences/lists (riffle shuffle permutations) -

recursion - Combinatorics in Scala: How to iterate/enumerate all possibilities to merge multiple sequences/lists (riffle shuffle permutations) -

updated question:

in original question did not know how refer next problem. clarify question, added following illustration wikipedia:

it turns out problem named after analogy: riffle shuffle permutations. based on terminology question becomes: how can iterate/enumerate riffle shuffle permutations in general case of multiple decks?

original question:

let's assume given multiple sequences , want merge these sequences 1 single sequence. resulting sequence should preserve order of original sequences. think of merging multiple stacks of cards (say seq[seq[t]]) 1 single stack (seq[t]) randomly drawing card (random) stack. input stacks should merged resulting stack. how can iterate or enumerate possible compositions of such resulting sequence?

to clarify: if have 3 stacks a, b, c (of 5 elements each) not want 6 possible arrangements of these stacks "all of a, of b, of c" , "all of a, of c, of b" etc. rather want possible compositions "1. of a, 1. of b, 2. of a, 1. of c, 3. of a, 2. of b, ...".

since i'm bit under weather today, first approach terribly ugly , produces duplicates:

def enumeratecompositions[t](stacks: seq[seq[t]], prefix: seq[t]): seq[seq[t]] = { if (stacks.length == 0) homecoming { seq(prefix) } stacks.zipwithindex.flatmap{ case (stack, stackind) => if (stack.length > 0) { val stackswithheadremoved = stacks.indices.map{ => 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) } } }

any thought how create more elegant , rid of duplicates?

let's phone call operation "to riffle". here clean idomatic solution:

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) // @ to the lowest degree 1 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 produce possible rifflings of 2 stacks. allrifflesseq take sequence of stacks , produce possible rifflings using fold. example, if allrifflesseq given stacks a, b, , c, first produces possible rifflings of , b , riffles c each of rifflings.

note allriffles consumes stacks space proportional length of shortest stack , allrifflesseq consumes stacks space bounded length of longest stack. also, returned list huge (combinatoric explosion) , consume lot of heap space. iterator based solution safer, much less pretty:

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 homecoming } 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 } }

scala recursion combinations permutation combinatorics