Select all permutations of N elements from the collection.

Permutation.scala

package com

import scala.collection.mutable.ArrayBuffer

object PermutationQuestion {

    def main(args: Array[String]): Unit = {
        val candidates = ArrayBuffer[Int](1, 3, 7, 5, 9)
        val count = 3
        val container = getAllPermutations(count, candidates)
        println(container.length)
        println(container.mkString("\n"))
    }

    def getAllPermutations(count: Int, candidates: ArrayBuffer[Int]): ArrayBuffer[ArrayBuffer[Int]] = {
        val container = ArrayBuffer[ArrayBuffer[Int]]()
        traverse(count, candidates, ArrayBuffer[Int](), container)
        container
    }

    /**
      * 递归函数
      *
      * @param count      可选个数
      * @param candidates 给定的待选数组
      * @param bag        前面递归层级中已经选择的 N，N'，N''... 的元素集合
      * @param container  用于存储可选类型的容器
      */
    def traverse(count: Int, candidates: ArrayBuffer[Int], bag: ArrayBuffer[Int], container: ArrayBuffer[ArrayBuffer[Int]]): Unit = {
        val candidatesLength = candidates.length
        if (candidatesLength >= count) {
            if (count.equals(1)) {
                for (item <- candidates) {
                    val finalBag = bag.clone()
                    finalBag += item
                    container += finalBag
                }
            } else {
                for ((item, index) <- candidates.zipWithIndex) {
                    val nextBag = bag.clone()
                    nextBag += item
                    val nextCandidates = candidates.slice(0, index) ++ candidates.slice(index + 1, candidatesLength)
                    traverse(count - 1, nextCandidates, nextBag, container)
                }
            }
        }
    }
}