如何生成可变大小正方形网格中所有M个点的无序组合解

Great question! Your createGrid function is totally suitable for this task—let's break down how to get the unordered point sets you need, where order doesn't affect solution validity.

1. Core Idea: Combinations Over Permutations #

First, let's clarify the key distinction here:

• Permutations: Generate all ordered arrangements of M points (this would include duplicates like [(1,1),(1,2)] and [(1,2),(1,1)], which you don't want).
• Combinations: Generate only unique unordered sets of M points—exactly what you need, since these treat swapped points as the same solution.

2. Implement Combinations (No External Dependencies) #

Haskell's standard library doesn't have a built-in combinations function, but it's straightforward to write a recursive version yourself:

combinations :: Int -> [a] -> [[a]]
combinations 0 _ = [[]]       -- Choosing 0 elements gives exactly one empty list
combinations _ [] = []        -- Can't pick elements from an empty list
combinations n (x:xs) = 
  map (x:) (combinations (n-1) xs)  -- Include x, then pick n-1 from the remaining points
  ++ combinations n xs              -- Skip x, pick all n points from the remaining list

This recursive logic ensures we never generate duplicate unordered sets—each unique group of points appears exactly once.

3. Pair with Your Grid Function #

Now just combine this with your createGrid to generate all valid solutions:

-- Your existing grid generator (works perfectly as-is!)
createGrid :: Int -> [(Int, Int)]
createGrid num = [ (x,y) | x <- [1..num], y <- [1..num]]

-- Generate all unordered sets of M points from an N×N grid
generateSolutions :: Int -> Int -> [[(Int, Int)]]
generateSolutions gridSize numPoints = combinations numPoints (createGrid gridSize)

Example Test Run #

For your 2×2 grid with 2 points:

main :: IO ()
main = print $ generateSolutions 2 2

This outputs all 6 valid unordered sets (since there are C(4,2) = 6 unique combinations):

[[(1,1),(1,2)],[(1,1),(2,1)],[(1,1),(2,2)],[(1,2),(2,1)],[(1,2),(2,2)],[(2,1),(2,2)]]

4. Optional: Use a Third-Party Library #

If you don't want to write your own combinations function, you can use the data-combinatorics package. Install it via Cabal first:

cabal install data-combinatorics

Then import and use the pre-built function:

import Data.Combinatorics (combinations)

generateSolutions :: Int -> Int -> [[(Int, Int)]]
generateSolutions gridSize numPoints = combinations numPoints (createGrid gridSize)

Why Your createGrid Is Perfect #

Your createGrid correctly enumerates every point in the grid by iterating x and y from 1 to num. This list is exactly what we need to feed into the combinations function—no tweaks required, even when you change the grid size N.

内容的提问来源于stack exchange，提问作者Jaffa