问题描述
我正在尝试输入实心方块"的数量,并在n x n板(清单列表)上生成这些方块的所有可能配置.空正方形表示为0,实心正方形为1.例如,在具有三个实心正方形的2x2网格上,可能的配置为:
I am trying to take an input number of "filled squares" and generate all possible configurations of those squares on an n by n board (list of lists). Empty squares are denoted 0, filled squares 1. For example, on a 2x2 grid with three filled squares, the possible configurations are:
[[1 1]
[1 0]]
[[1 1]
[0 1]]
[[1 0]
[1 1]]
[[0 1]
[1 1]]
函数每次生成这些配置之一时,都会对其进行复制并将其附加到列表(configList)中.这是我的想法(如下),但是当我开始为它编写代码时,它似乎比它必须的复杂得多.对于有x个帐篷(填充的正方形代表帐篷)的n x n板,有没有更有效的方法,我将如何在python中实现呢?
Each time the function generates one of these configurations it copies it and appends it to a list (configList). Here is my idea (below), but when I started writing the code for it it seemed monstrously more complex than it had to be. Is there a more efficient way to do this for an n by n board with x number of tents (filled squares represent tents), and how would I implement this in python?
def findConfigs(config):
configList = []
place tents sequentially on the board
loop:
find last tent's location
for each following position on the board:
move last tent to this position
newConfig = deepcopy(config)
configList.append(newConfig)
# last tent has reached the end of the board, so-
find the previous tent
if next position is not occupied by the following tent:
move it forward
move following tents directly after
else: # the previous tent cannot move any further
find next previous tent
if next position is not occupied by the following tent...
go back to loop
return configList
推荐答案
您可以使用组合
生成 0
s
>>> from itertools import combinations
>>> list(combinations(range(4), 1))
[(0,), (1,), (2,), (3,)]
只需将数字0、1、2、3映射到2x2网格上即可.
Just map the numbers 0,1,2,3 onto your 2x2 grid.
一个更大的例子可能更令人信服
A larger example is probably more convincing
>>> list(combinations(range(9), 2))
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (4, 5), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8), (6, 7), (6, 8), (7, 8)]
下面是映射到2D列表的示例
Here's an example mapping to a 2D list
>>> from itertools import product, combinations
>>> n = 3 # 3x3
>>> m = 2 # 2 tents
>>> for i in combinations(range(n*n), m):
... print [[0 if x*n+y in i else 1 for x in range(n)] for y in range(n)]
...
[[0, 1, 1], [0, 1, 1], [1, 1, 1]]
[[0, 1, 1], [1, 1, 1], [0, 1, 1]]
[[0, 0, 1], [1, 1, 1], [1, 1, 1]]
[[0, 1, 1], [1, 0, 1], [1, 1, 1]]
[[0, 1, 1], [1, 1, 1], [1, 0, 1]]
[[0, 1, 0], [1, 1, 1], [1, 1, 1]]
[[0, 1, 1], [1, 1, 0], [1, 1, 1]]
[[0, 1, 1], [1, 1, 1], [1, 1, 0]]
[[1, 1, 1], [0, 1, 1], [0, 1, 1]]
[[1, 0, 1], [0, 1, 1], [1, 1, 1]]
[[1, 1, 1], [0, 0, 1], [1, 1, 1]]
[[1, 1, 1], [0, 1, 1], [1, 0, 1]]
[[1, 1, 0], [0, 1, 1], [1, 1, 1]]
[[1, 1, 1], [0, 1, 0], [1, 1, 1]]
[[1, 1, 1], [0, 1, 1], [1, 1, 0]]
[[1, 0, 1], [1, 1, 1], [0, 1, 1]]
[[1, 1, 1], [1, 0, 1], [0, 1, 1]]
[[1, 1, 1], [1, 1, 1], [0, 0, 1]]
[[1, 1, 0], [1, 1, 1], [0, 1, 1]]
[[1, 1, 1], [1, 1, 0], [0, 1, 1]]
[[1, 1, 1], [1, 1, 1], [0, 1, 0]]
[[1, 0, 1], [1, 0, 1], [1, 1, 1]]
[[1, 0, 1], [1, 1, 1], [1, 0, 1]]
[[1, 0, 0], [1, 1, 1], [1, 1, 1]]
[[1, 0, 1], [1, 1, 0], [1, 1, 1]]
[[1, 0, 1], [1, 1, 1], [1, 1, 0]]
[[1, 1, 1], [1, 0, 1], [1, 0, 1]]
[[1, 1, 0], [1, 0, 1], [1, 1, 1]]
[[1, 1, 1], [1, 0, 0], [1, 1, 1]]
[[1, 1, 1], [1, 0, 1], [1, 1, 0]]
[[1, 1, 0], [1, 1, 1], [1, 0, 1]]
[[1, 1, 1], [1, 1, 0], [1, 0, 1]]
[[1, 1, 1], [1, 1, 1], [1, 0, 0]]
[[1, 1, 0], [1, 1, 0], [1, 1, 1]]
[[1, 1, 0], [1, 1, 1], [1, 1, 0]]
[[1, 1, 1], [1, 1, 0], [1, 1, 0]]
这篇关于Python在“木板"上生成所有可能的数字配置.的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!