Print all possible combinations of 2 arrays maintaining order

Question

I want to print all the possible combinations that contain all the elements of each array and also maintains the order of each individual array. For example:

Input:
a= [1, 2]
b= [3, 4]

Output:
[1, 2, 3, 4]
[1, 3, 2, 4]
[3, 4, 1, 2]
[3, 1, 4, 2]
[1, 3, 4, 2]
[3, 1, 2, 4]

What I mean by maintaining the order is to maintain the order of each individual array, so 2 never appears before 1 and 4 never appears before 3.

I'd like to program this using Kotlin or Java.

I maintain the order of each individual array (1 is never after 2 and 3 is never after 4) — dfortu, May 31 '22 at 09:04

score 0 · Answer 1 · answered May 31 '22 at 10:55

The first part is a regular permutations function for a list of ints. The second part concatenates the two lists, creates the permutations, and then filters out the solutions where the elements of listA do not appear in the same order and the same check is made for the elements in listB:

fun List<Int>.permutations(): List<List<Int>> {
  if (isEmpty()) return listOf(emptyList())
  return indices.fold(mutableListOf()) { result, i ->
    (result + (this - this[i])
      .permutations()
      .fold(mutableListOf()) { acc, item ->
        acc.add(item + this[i])
        acc
      }
    ).toMutableList()
  }
}

val listA = listOf(1, 2)
val listB = listOf(3, 4)

val permutations = (listA + listB)
  .permutations()
  .filter { list ->
    list
      .filter { int -> int in listA }
      .map { int -> listA.indexOf(int) }
      .zipWithNext { int1, int2 -> int1 <= int2 }
      .all { isTrue -> isTrue }
    &&
    list
      .filter { int -> int in listB }
      .map { int -> listB.indexOf(int) }
      .zipWithNext { int1, int2 -> int1 <= int2 }
      .all { isTrue -> isTrue }
  }

permutations.forEach(::println)

Output:

[3, 4, 1, 2]
[3, 1, 4, 2]
[1, 3, 4, 2]
[3, 1, 2, 4]
[1, 3, 2, 4]
[1, 2, 3, 4]

Note: The solution might not work fast enough for larger lists as this creates all permutations and then filters most of them out.

Print all possible combinations of 2 arrays maintaining order

1 Answers1

Linked