Python在“木板"上生成所有可能的数字配置. [英] Python generate all possible configurations of numbers on a "board"

问题描述

我正在尝试输入实心方块"的数量，并在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在“木板"上生成所有可能的数字配置.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！