3
\$\begingroup\$

Introduction

This code was part of one of my projects where it was used to generate boolean input values for truth tables. I have since generalized it for combinations of variables with only 2 values, and added a dash of general Scala-isms. This has been unit-tested with ScalaTest, and has proper documentation.

I rewrote my original code which used bitmasking and shifts because I thought it was too "magical", i.e., difficult to understand at first glance. The bitmasking method also does not give a proper ordering of the values as I would have liked it, which this method does.

This also embodies the concept of a multi-line expression-bodied method.

Notes

My IDE (IntelliJ Idea) recommends not using superfluous parentheses, but I leave them in for clarity.

I would like reviews on any and all aspects of the code and documentation, including but not limited to performance (not really important over clarity to me here, otherwise I'd have used the bitmasking version instead), clarity and idiomatic nature of the code.

Running

Just copy into a file with extension .scala and run it in the Scala REPL as a script. Example usage:

allCombinations(4, true, false) // duplicates the use case I had in my project.

(Run the above in the REPL after the script as beem loaded (scala <file name>.scala, or put it at the bottom of the file <file name>.scala)


Code

/**
    * Generates all possible distinct combinations of `n` variables which have only 2 values,
    * `value` and `alternativeValue`.
    *
    * @param n                the number of variables to generate combinations for
    * @param value            one possible value for a variable
    * @param alternativeValue the other possible value for a variable
    * @return all possible distinct combinations of `n` booleans
    */
def allCombinations[T](n: Int, value: T, alternativeValue: T): Seq[Seq[T]] = {
    for (i <- 0 to n) yield {
      // Make the first i values true and the rest false,
      // and then take all their permutations.
      // This gives us all the required combinations.
      (Seq.tabulate(n)(x => 
                       if (x < i) value 
                       else alternativeValue)
       ).permutations
    } // flatten 1 level into a 1-deep list
}.flatten
\$\endgroup\$
2
\$\begingroup\$

Why is the function named allCombinations? The "all" seems superfluous. Also, it's actually returning permutations rather than combinations, so the second half isn't really accurate either. I suggest naming it something else entirely, though: product, based on the function in Python's itertools module that does something similar. As for the first parameter, I find dims (or dimensions) to be more descriptive than n.

Why limit yourself to two possible values? Why not also support a tri-state, for example? You could make values variadic. As a bonus, you wouldn't have to manually toggle between value and alternativeValue; you could just use normal iteration tools like .map.

def product[T](dims: Int, values: T*): Seq[Seq[T]] = {
  dims match {
    case 0 => Seq()
    case 1 => values.map(Seq(_))
    case _ => {
      val lesserProduct = product(dims - 1, values:_*)
      values.flatMap(v => lesserProduct.map(_.+:(v)))
    }
  }
}

Note that the ordering convention is different from yours; i.e. product(4, false, true) is equivalent to allCombinations(4, true, false). I don't consider that to be a drawback.

\$\endgroup\$
  • \$\begingroup\$ This is not tail-recursive. Might cause a performance hit or stack overflows with higher dimensions; otherwise good \$\endgroup\$ – Tamoghna Chowdhury Mar 14 '17 at 4:48
  • \$\begingroup\$ Plus, it looks horrible. ;). But that's life in Scala! \$\endgroup\$ – Tamoghna Chowdhury Mar 14 '17 at 4:49
  • \$\begingroup\$ How many dimensions could you realistically expect, though? \$\endgroup\$ – 200_success Mar 14 '17 at 4:49
  • \$\begingroup\$ In my humble opinion, it looks less horrible than yours. =) \$\endgroup\$ – 200_success Mar 14 '17 at 4:49
  • \$\begingroup\$ Also, have you confirmed that this produces the same order of results as mine? \$\endgroup\$ – Tamoghna Chowdhury Mar 14 '17 at 4:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.