object PermutationsAndCombinations {
// Print a sequence of characters
def printSeq(seq: Seq[Char]): Unit =
println(seq.mkString(" "))
// Recursive function to generate permutations
def permute(arr: Array[Char], l: Int, r: Int): Unit = {
if (l == r) {
printSeq(arr)
} else {
for (i <- l to r) {
swap(arr, l, i)
permute(arr, l + 1, r)
swap(arr, l, i) // backtrack
}
}
}
// Swap two elements in an array
def swap(arr: Array[Char], i: Int, j: Int): Unit = {
val tmp = arr(i)
arr(i) = arr(j)
arr(j) = tmp
}
// Generate all combinations using bitmask
def generateCombinations(arr: Array[Char]): Unit = {
val size = arr.length
for (mask <- 1 until (1 << size)) {
val combo = for {
i <- 0 until size
if (mask & (1 << i)) != 0
} yield arr(i)
println(combo.mkString(" "))
}
}
def main(args: Array[String]): Unit = {
val input = Array('a', 'b', 'c')
val size = input.length
println("All permutations:")
permute(input.clone(), 0, size - 1)
println("\nAll combinations:")
generateCombinations(input)
}
}
/*
run:
All permutations:
a b c
a c b
b a c
b c a
c b a
c a b
All combinations:
a
b
a b
c
a c
b c
a b c
*/
