컴 톨션을위한 순열

Question

그래서 스칼라로 이해를 위해 순열을 생성하는 방법을 알아 내는데 약간의 문제가 있습니다. 문제는 보드에 조각을 넣어 고유 한 보드 구성 목록을 생성하는 기능을 갖고 싶다는 것입니다. 그래서 제가 작성한 코드는 다음과 같습니다 :

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))) 

할 수 있지만 여전히 난 정말 그들이 생성 된 후 바로 일을 필터링하고 있고 추가주기를하고있는 중이 야. 내가 그것을 피할 수있는 영리한 방법이 있나. 어떤 제안도 환영받는 것 이상

Answer 1

트릭은 보드 위치에 순서를 정의하는 것이므로 P1> P2 인 경우 조합 (P1, P2)을 고려하지 않을 것입니다. 2 차원 (sizeX x sizeY) 집합의 순서는 함수 def rank(x: Int, y: Int) = x * sizeY + y에 의해 주어질 수 있습니다. 이제는 위치 간의 순서를 계산하고 보드 위치를 순서대로 생성 할 수 있습니다. 즉, P1을 배치하고 나면 P2> P1의 추가 이동 P2 만 고려하십시오.