如何实现这个算法在Python？ [英] how to implement this algorithm in python?

问题描述

这是某种类型的笛卡尔乘积是从最初的固定长度的一系列整数催生，产生额外的系列，采用由规定的 N 符号所决定的规则额外的序列号必须遵循。

This is some type of cartesian product that is spawned from an initial fixed length series of integers, generate additional series, using the rule dictated by the symbol that dictates the n number of additional series that must follow.

例如（ ^ 产生额外的1系列， * 产生额外的3系列）

for example (^ produces additional 1 series, * produces additional 3 series)

1 0^ 1* 1

生成

1 0 2 1
1 0 3 1
1 0 4 1 (we stop here because we have produced 3 additional series)

1 1 1* 1 (we have produced an additional series from the `^` symbol. still have the `*`)

1 1 2 1
1 1 3 1 
1 1 4 1

再比如，现在一个更大的长度系列和其他规则。

Another example, now with a larger length series and additional rule.

1 0^ 1* 0^ 1

生成

1 0 2 0 1
1 0 3 0 1
1 0 4 0 1

1 0^ 1* 1 1

1 0 2 1 1 
1 0 3 1 1 
1 0 4 1 1 

1 1 1* 1 1 

1 1 2 1 1 
1 1 3 1 1 
1 1 4 1 1 

我只是无聊，开始写一整系列这样的数字在纸上，并好奇地想知道，如果已经有一个算法或实施产生一系列的整数组成的这样的序列。需要注意的是有一系列产生附加系列，使其更容易理解之间新行。

I was just bored and started writing a whole series of numbers like this on paper and was curious to know if there was already an algorithm or implementation which generates such sequence of series of integers. Note that there's new line between series that generates additional series to make it easier to understand.

推荐答案

您可以使用的 itertools.product 以笛卡尔乘积一般。具体而言，我会实现你的算法在两个单独的步骤：

You can use itertools.product for Cartesian products in general. Specifically, I would implement your algorithm in two separate steps:

1. 分析输入的字符串（如1 0 ^ 1 * 0 ^ 1）成整数列表的列表;和
2. 产生列表的列表中的产物。

1. Parse the input string (e.g. "1 0^ 1* 0^ 1") into a list of lists of integers; and
2. Produce the product of the list of lists.

有一个相对简单的基于生成器的实现，具有辅助功能为清楚起见，将是这样的：

A relatively simple generator-based implementation, with a helper function for clarity, would look like:

def algorithm(input_):
    # Step 1
    instructions = []
    for s in input_.split():
        try:
            instructions.append([int(s)])
        except ValueError:
            instructions.append(list(values(s)))
    # Step 2
    for prod in itertools.product(*instructions):
        yield prod

def values(s):
    RULES = {'*': 4, '^': 2}
    n = int(s[:-1])
    for x in range(RULES[s[-1]]):
        yield n + x

例如：

>>> print("\n".join(" ".join(map(str, t)) for t in algorithm("1 0^ 1* 1")))
1 0 1 1
1 0 2 1
1 0 3 1
1 0 4 1
1 1 1 1
1 1 2 1
1 1 3 1
1 1 4 1

您将不得不与它鼓捣得到precise顺序（你似乎有一个运营商，而不是左到右，precedence）和格式（如组之间的空格）你寻找。

You will have to tinker with it to get the precise order (you appear to have an operator, rather than left-to-right, precedence) and formatting (e.g. spaces between groups) you're looking for.

这篇关于如何实现这个算法在Python？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！