如何在python中实现此算法？

一尘不染

如何在python中实现此算法？

algorithm

这是一种笛卡尔乘积，它是从固定长度的整数初始序列中衍生出来的，并使用由符号指示的规则来生成附加序列，该符号指示n必须遵循的附加序列的数量。

例如（^产生附加的1系列，*产生附加的3系列）

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

另一个示例，现在具有更大的长度序列和附加规则。

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

我很无聊，开始在纸上写出这样的整数序列，并想知道是否已经有算法或实现生成这样的整数序列。请注意，系列之间有一条新的线，可以生成更多的系列以使其更易于理解。

阅读 297

2020-07-28

共1个答案

一尘不染

itertools.product通常，您可以使用笛卡尔积。具体来说，我将分两个步骤实施您的算法：

将输入字符串（例如"1 0^ 1* 0^ 1"）解析为整数列表；和
产生清单清单的产品。

一个相对简单的基于生成器的实现，带有一个帮助函数，为了清楚起见，它看起来像：

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

您将不得不修改它以获得所需的精确顺序（您似乎拥有一个运算符，而不是从左至右的优先级）和格式（例如，组之间的空格）。

2020-07-28