i'm looking for an algorithm or the name of my problem (i assume this is very old and nothing new). I want to find all the unique combinations of 5 filled cells in a 5x12 grid.
example:
1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
1|0|0|0|0|0|0|0|0|0|0|0
1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
1|0|0|0|0|0|0|0|0|0|0|0
-----------------------
0|0|1|0|0|0|0|0|0|0|0|0
1|1|1|1|1|0|0|0|0|0|0|0
-----------------------
0|0|0|0|0|0|0|0|0|0|0|0
-----------------------
0|0|0|0|0|0|0|0|0|0|0|0
-----------------------
0|0|0|0|0|0|0|0|0|0|0|0
-----------------------
0|0|0|0|0|0|0|0|0|0|0|0
this is also valid
and so on. Each occupied cell would be represented as an (X,Y)-Tuple
The corresponding formula for the amount of unique combinations is n over k - binomialcoefficient (or something like that) which would be something like 5.1 million unique combinations if i recall correctly.
Most other similar questions here or on other platforms restrict it some way that each row must have exactly one cell occupied. For my special case thats not true and the reason for my issue.
This is my first question here and i hope someone can help me solve this as i cannot find an idea for a systematic approach
I suggest you use this easy and understandable solution: First of all, give every cell an index so we could talk about 60-cells-length-list instead of a 2-diemensional board. I want you to initial such an indexes-list: [1, 2, 3... 59, 60] Now, you basically need every k-size (in your case it's five) combination of those indexes. The rest is pretty easy. Use this code:
def findsubsets(s, n):
return list(itertools.combinations(s, n))
While s is your list and n is the k (5 for you). This function returns every possible combination of 5 numbers from the list. Use every combination to fill the right cells with 1's and the rest with 0's. Hope it helped you. Good Luck!