permutations

permutations.scala

def permutationRecursion(a: List[Int]) = {
  import scala.collection.mutable
  val results = mutable.ListBuffer[List[Int]]()
  
  def p(curr: List[Int], remaining: List[Int]): Unit = {
     if (remaining.isEmpty) {
       results += curr
     }
     else {
      for (i <- remaining) {
        p(curr :+ i, remaining diff List(i))
      }
     }
  }

  def p2(curr: List[Int]): Unit = {
     if (curr.size == a.size) {
       results += curr
     }
     else {
      for { i <- a if (!curr.contains(i)) } {
        p2(curr :+ i)
      }
     }
  }
  
  p2(List.empty)
  results
}

def permutationIterative(a: List[Int]) = {
  import scala.collection.mutable
  val results = mutable.ListBuffer[List[Int]]()
  val currStack = mutable.Queue[List[Int]]()
  val remainingStack = mutable.Queue[List[Int]]()
  currStack.enqueue(List.empty)
  remainingStack.enqueue(a)
  
  while(currStack.nonEmpty && remainingStack.nonEmpty) {
    val curr = currStack.dequeue()
    val remaining = remainingStack.dequeue()
    
    if (remaining.isEmpty) {
      results += curr
    }
    else {
      for (i <- remaining) {
        currStack.enqueue(curr :+ i)
        remainingStack.enqueue(remaining diff List(i))
      }
    }
  }
  
  results
}

def permutationIterator(a: List[Int]) = new Iterator[List[Int]] {
  import scala.collection.mutable
  var nextValue: Option[List[Int]] = None
  var nextSet: Boolean = false
  val currStack = mutable.Queue[List[Int]]()
  currStack.enqueue(List.empty)
  
  def hasNext: Boolean = {
    if (!nextSet)
      doNext()
    nextValue.nonEmpty
  }
  
  def next(): List[Int] = {
    if (!nextSet)
      doNext()
    nextSet = false
    nextValue.get
  }
 
  def doNext(): Unit = {
    var foundNext = false
    while(currStack.nonEmpty && !foundNext) {
      val curr = currStack.dequeue()

      if (curr.size == a.size) {
        nextValue = Some(curr)
        foundNext = true
      }
      else {
        for { i <- a if !curr.contains(i) } {
          currStack.enqueue(curr :+ i)
        }
      }
    }
    
    if (!foundNext)
      nextValue = None
    
    nextSet = true
  }
}

println(permutationRecursion(List(1,2,3)))
println(permutationIterative(List(1,2,3,4)))

val it = permutationIterator(List(1,2,3))
it.next()
it.next()
it.next()
it.next()
it.next()
it.next()
it.nextOption()