How can I generate every possible solution of a varied size grid which has n points-CodePudding

To give overall context, I have a 2d grid of size N (the size is known but can vary and is always a square i.e x axis = y axis) and M points on the grid that I'm trying to find (the amount of points is known but their locations are not). I want to iterate through every possible solution for said grid. Also the points don't have to be in a specific order, so

[(1,1),(1,2)] 
is the same as 
[(1,2),(1,1)]

So for example assume the grid was a 2x2 and their was 2 points. Then all the possible solutions would be

[(1,1),(1,2)]
[(1,1),(2,1)]
[(1,1),(2,2)]
[(1,2),(2,1)]
...and so on...

I'm trying to create a function that will output these to me.

I know the function below can create me a full grid, but I don't know how to use this to generate all the possible point locaitons. And whether this grid is even useful in the first place

createGrid :: Int -> [(Int, Int)]
createGrid num = [ (x,y) | x <- [1..num], y <- [1..num]]

Any help would be appreciated

CodePudding user response：

It sounds like you just want a list of the unique ways to choose M items from a list (grid) of N*M items. You already know how to generate this list, so all you need is the ways to choose K items from a list. This is a well-trodden path; for example, see Function to generate the unique combinations of a list in Haskell.

In general it is useful to try to do this sort of splitting up: break your program into smaller pieces and see how many of them are easy to solve. If you try to do everything all at once in one function, you end up repeating work and often wind up with a function that is difficult to read.

CodePudding user response：

For a given grid, if m is 0, then we return the empty list, when m is greater than 0, then we yield a point and recurse on the rest of the list, so:

possibleGrids :: Int -> Int -> [[(Int, Int)]]
possibleGrids n mm = go mm 1 0
    where go 0 _ _ = [[]]
          go m i j = [(x, y) : tl | x <- [i .. n], y <- [1 .. n], x > i || y > j, tl <- go (m-1) x y]

The first parameter here is n, the size of the grid. The second one is m, the number of points to mark. For a 2×2 grid, this gives us:

ghci> possibleGrids 2 0
[[]]
ghci> possibleGrids 2 1
[[(1,1)],[(1,2)],[(2,1)],[(2,2)]]
ghci> possibleGrids 2 2
[[(1,1),(1,2)],[(1,1),(2,1)],[(1,1),(2,2)],[(1,2),(2,1)],[(1,2),(2,2)],[(2,1),(2,2)]]

The code uses symmetry breaking, so it will not mark twice (or more) the same point, nor will it provide the list of points in a different order.