How to generate all permutations of splitting an array to two subarrays in Scala?

Question

Given an array, I would like to split it into two non-empty subarrays.

For example, given the following array:

val nums = Array(1, 2, 3, 4)

I would like to generate the following unique permutations:

(Array(1), Array(2, 3, 4))
(Array(2), Array(1, 3, 4))
(Array(1, 2), Array(3, 4))
(Array(3), Array(1, 2, 4))
(Array(1, 3), Array(2, 4))
(Array(2, 3), Array(1, 4))
(Array(1, 2, 3), Array(4))

The permutations are unique in the sense that if a given split is just a mirror of another split, I only need to keep one of them. Also, the order of elements in the subarrays do not matter.

See below for a working solution: https://stackoverflow.com/a/57262577/5767875. But I believe a more elegant and functional solution exists.

score 2 · Accepted Answer · answered Jul 30 '19 at 00:17

def splits(xs: Array[Int]): Array[(Array[Int], Array[Int])] = {
  val startSplit: Array[(Array[Int], Array[Int])] = Array((Array(xs.head), Array.empty))
  xs.tail.foldLeft(startSplit) { (splits, x) =>
    splits.flatMap {
      case (left, right) => Array((x +: left, right), (left, x +: right))
    }
  }.tail
}

The basic idea is that if you know all of the splits for the first N elements, then there are twice as many splits for N+1 elements: you can add the new element to either the left or the right for every split and obtain a new split. That's what's happening in the foldLeft call.

The only small wrinkles are: this would generate "mirror" splits, so the starting point just always has the first element on the left. And: at the end you have one extra output which is every element on the left, so the final call to .tail gets rid of that.

Note that the performance of this is probably pretty horrible, since scala arrays don't have efficient appends and such so every operation makes a copy. You could replace Array with List in the above code and get something better. If you really need to deal with arrays you could then just convert (.toList / .toArray)

Very nice solution, @Joe K! You are right using `List` can speed up the performance. — cwl, Jul 30 '19 at 22:35

score 0 · Answer 2 · answered Jul 29 '19 at 23:46

Based on this SO post, below is a version of Scala code:

import scala.collection.mutable.ArrayBuffer

def generateSplitPermutations(nums: Array[Int]): Array[(Array[Int], Array[Int])] = {
  var results: List[(Array[Int], Array[Int])] = List()

  var flags = Array.fill(nums.length)(false)
  var done = false
  while (!done) {

    var a = ArrayBuffer[Int]()
    var b = ArrayBuffer[Int]()
    for ((bool, i) <- flags.zipWithIndex) {
      if (bool)
        a += nums(i)
      else
        b += nums(i)
    }

    if (a.length > 0 && b.length > 0) {
       results = results :+ (a.toArray, b.toArray)
    }

    if (flags.map(x => if (x) 1 else 0).sum == nums.length / 2 + 1) {
      done = true
    }

    // if done is true, the following code block won't matter
    var ok = false
    for (i <- 0 until nums.length if !ok) {
      flags(i) = !flags(i)
      if (flags(i))
        ok = true
    }
  }

  results.toArray
}

val nums = Array(1, 2, 3, 4)
generateSplitPermutations(nums)

outputs:

scala> generateSplitPermutations(nums)
res16: Array[(Array[Int], Array[Int])] = Array((Array(1),Array(2, 3, 4)), (Array(2),Array(1, 3, 4)), (Array(1, 2),Array(3, 4)), (Array(3),Array(1, 2, 4)), (Array(1, 3),Array(2, 4)), (Array(2, 3),Array(1, 4)), (Array(1, 2, 3),Array(4)))

Is there a more Scala/functional way of achieving this?

How to generate all permutations of splitting an array to two subarrays in Scala?

2 Answers2