Permutations with for comprehensons

Question

So I have a bit of a problem figuring out how to generate permutations with Scala for comprehensions. The problem is that I want to have function that generates a list of unique board configurations by putting pieces on the board. So the code that I have written is:

case class Piece(x:Int,y:Int)

def positionNotOccupied(piece: Piece,board: Seq[Piece]): Boolean = {
  !board.map(piece => (piece.x,piece.y)).contains((piece.x,piece.y))
}

def placePiece(sizeX:Int, sizeY:Int, numPieces:Int): List[List[Piece]] = numPieces match {
  case 0 => List(Nil)
  case _ => for {
    pieces <- placePiece(sizeX,sizeY,numPieces - 1)
    x <- 1 to sizeX
    y <- 1 to sizeY
    piece =  Piece(x, y)
    if positionNotOccupied(piece,pieces)
  } yield piece :: pieces
}

I want to assume that all pieces are the same so I am effectively looking for unique configurations. That is, P1,P2 == P2,P1. However if I invoke that for a board of size 2X1 and I want to place two pieces on it, I get the following output:

placePiece(2,1,2)
List(List(Piece(2,1), Piece(1,1)), List(Piece(1,1), Piece(2,1)))

I get two configurations but they really are the same. Of course I can always do

placePiece(2,1,2).map(_.toSet).distinct
List(Set(Piece(2,1), Piece(1,1)))

which solves the problem, but still I really am just filtering things after they have been generated and am doing the additional cycles. Is there any clever way that I can avoid that. Any suggestions are more than welcomed

Answer 1

The trick would be to define an order on the positions of the board, so that you would never consider combination (P1, P2) where P1 > P2. An order on a two-dimensional (sizeX x sizeY) set can be given by function def rank(x: Int, y: Int) = x * sizeY + y. So now you can compute order among the positions, and generate board positions in order, i.e. once you have placed P1, only consider further moves P2 where P2 > P1.