given a list of entities and goals find all possible goals/entities associations where a goal can only be used once / published by https://github.com/dacr/code-examples-manager #ce17c405-3ae0-406e-b92e-fb02bd6c2928/982f7d8811619bb60dcacf1ffdaa94c6d5bf63db

algo-solutions-combinations-list.sc

// summary : given a list of entities and goals find all possible goals/entities associations where a goal can only be used once
// keywords : scala, algorithm, solutions, combinations, @testable
// publish : gist
// authors : David Crosson
// license : Apache NON-AI License Version 2.0 (https://raw.githubusercontent.com/non-ai-licenses/non-ai-licenses/main/NON-AI-APACHE2)
// id : ce17c405-3ae0-406e-b92e-fb02bd6c2928
// created-on : 2020-05-18T11:53:14Z
// managed-by : https://github.com/dacr/code-examples-manager
// run-with : scala-cli $file

// ---------------------
//> using scala "3.4.2"
//> using dep "org.scalatest::scalatest:3.2.16"
//> using objectWrapper
// ---------------------

import org.scalatest._, flatspec._, matchers._

/**
 * Compute all possible solution goals for your entities which combine for each input entity a distinct goal
 * It adjusts its behavior to the number of available goals and entities, if more entities than goals it will
 * for example not use all entities on a generated solution.
 *
 * @param entities
 * @param goals
 * @tparam E entity type
 * @tparam G goal type
 * @return Iterator on each possible solution
 */
def solutions[E, G](entities: List[E], goals: List[G]): Iterator[List[(E, G)]] = {
  if (entities.isEmpty || goals.isEmpty) Iterator.empty
  else if (entities.size == 1) goals.map(goal => (entities.head -> goal) :: Nil).iterator
  else if (goals.size == entities.size) entities.permutations.map(_.zip(goals))
  else if (goals.size < entities.size) entities.combinations(goals.size).flatMap(_.permutations).map(_.zip(goals))
  else goals.combinations(entities.size).flatMap(_.permutations).map { goalComb => entities.zip(goalComb) }
}


/*
 All unit tests
 */

class SolutionsTest extends AnyFlatSpec with should.Matchers {
  override def suiteName: String = "SolutionsTest"

  "solutions" should "return nothing when no goals are known" in {
    solutions(1 :: Nil, Nil).toList shouldBe empty
    solutions(1 :: 2 :: Nil, Nil).toList shouldBe empty
  }

  it should "return nothing when no entities are available for defined goals" in {
    solutions(Nil, "A"::Nil).toList shouldBe empty
    solutions(Nil, "A"::"B"::Nil).toList shouldBe empty
  }

  it should "list all solutions with less entities than goals" in {
    solutions(1 :: Nil, "A" :: "B" :: Nil).toList should contain allOf(
      (1, "A") :: Nil,
      (1, "B") :: Nil
    )
  }
  it should "list all solutions when we have the same number of goals and entities" in {
    solutions(1 :: Nil, "A" :: Nil).toList should contain (
      (1, "A") :: Nil
      )
    solutions(1 :: 2 :: Nil, "A" :: "B" :: Nil).toList should contain allOf (
      (1, "A") :: (2, "B") :: Nil,
      (2, "A") :: (1, "B") :: Nil,
      )
  }
  it should "list all solutions with more entities than goals" in {
    solutions(1 :: 2 :: 3 :: Nil, "A" :: "B" :: Nil).toList should contain allOf(
      (1 -> "A") :: (2 -> "B") :: Nil,
      (2 -> "A") :: (1 -> "B") :: Nil,
      (1 -> "A") :: (3 -> "B") :: Nil,
      (3 -> "A") :: (1 -> "B") :: Nil,
      (2 -> "A") :: (3 -> "B") :: Nil,
      (3 -> "A") :: (2 -> "B") :: Nil
    )
  }
}

org.scalatest.tools.Runner.main(Array("-oDF", "-s", classOf[SolutionsTest].getName))