Last active
July 8, 2018 09:36
-
-
Save dailybird/c61dead700f1093897f265d290be5475 to your computer and use it in GitHub Desktop.
Select all combinations of N elements from the collection.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com | |
import scala.collection.mutable.ArrayBuffer | |
object CombinationQuestion { | |
def main(args: Array[String]): Unit = { | |
val candidates = ArrayBuffer[Int](1, 3, 7, 5, 9) | |
val count = 3 | |
val container = getAllCombinations(count, candidates) | |
println(container.length) | |
println(container.mkString("\n")) | |
} | |
def getAllCombinations(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 = { | |
if (count <= candidates.length) { | |
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(index + 1, candidates.length) | |
traverse(count - 1, nextCandidates, nextBag, container) | |
} | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment