用于理解的排列

所以我有一个问题想出如何用Scala产生理解的排列组合。问题是我想要具有通过在板上放置棋子来生成独特棋盘配置列表的功能。所以我写的代码是：用于理解的排列

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 
}

我想假设所有部件都是相同的，所以我正在有效地寻找独特的配置。即P1，P2 == P2，P1。但是，如果我调用，对于尺寸2X1的董事会，我想在其上放置两片，我得到下面的输出：

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

我得到两个配置，但他们真的是相同的。当然，我总是可以做

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

解决了这个问题，但我仍然真的我只是过滤的事情，他们已经产生之后我做了额外的周期。有没有什么聪明的方法可以避免这种情况？任何建议都非常受欢迎

来源

2017-03-17 Zahari

诀窍是定义董事会职位的订单，以便您永远不会考虑P1> P2的组合（P1，P2）。二维（sizeX x sizeY）集上的订单可以通过函数def rank(x: Int, y: Int) = x * sizeY + y给出。因此，现在您可以计算这些头寸之间的顺序，并按顺序生成板面位置，即一旦放置了P1，就只考虑P2> P1的进一步移动P2。

来源

2017-03-17 15:15:11 radumanolescu

这非常有用。所以我假设，如果我想实现它多于一种类型的作品，我将不得不将它的类型也归入排名函数中？ – Zahari

当然。您可以将“片段类型”想象为三维空间中的Z坐标。因此，您可以将排名函数修改为像'z * sizeX * sizeY + x * sizeY + y' - 其中z是“片段类型”的索引到大小为Z的项目的有限列表中 – radumanolescu

工作得很好。非常感谢！ – Zahari

用于理解的排列

回答

相关问题