python - 来自模型的嵌套排列

Question

我正在编写一个程序，它采用字符串的排列“模型”，并根据该模型输出所有排列。该模型看起来像这样:

model = Mix([
    [
        "this",
        PickOne(["is", "isn't"])
    ],
    PickOne([
        Mix([
            "absolutely",
            "great"
        ])
    ])
])

在输出的排列中，

1. list objects会依次输出包含的对象
2. Mix objects 将以所有可能的最大长度(包括零)以各种可能的顺序输出包含的对象
3. PickOne objects 一次只会输出一个包含它的对象

因此，上述示例的期望输出为:

[
    ["this", "is"],
    ["this", "isn't"],
    ["this", "is", "absolutely"],
    ["this", "is", "great"],
    ["this", "isn't", "absolutely"],
    ["this", "isn't", "great"],
    ["absolutely"],
    ["great"],
    ["absolutely", "this", "is"],
    ["great", "this", "is"],
    ["absolutely", "this", "isn't"],
    ["great", "this", "isn't"],
    []
]

到目前为止，我已经实现了 Mix 的排列像这样上课:

class Mix(list):
    def __init__(self, *args, **kwargs):
        super(Mix, self).__init__(*args, **kwargs)
        self.permutations = []
        for L in range(0, len(self)+1):
            for subset in itertools.combinations(self, L):
                subset_permutations = itertools.permutations(subset)
                self.permutations.extend(subset_permutations)

和我的 PickOne类就是这样

class PickOne(list):
    pass

我计划仅在我的主要功能中进行测试并进行相应处理 (if type(obj) is PickOne: ...)。

itertools为更简单的用例提供简化和效率，但是我不知道它将如何帮助我实现这个实现(除了我已经在 Mix 中实现的)。关于如何 itertools 的任何想法可以用来帮助上述的 Pythonic 实现吗？

Answer 1

我在思考所有这些组合时遇到了一些麻烦，但我认为您的 Mix 类还必须产生所有这些 排列的 product 。我创建了一个类似的模型来对此进行测试。这可能与您的有点不同，但应该很容易适应:

class CombModel:
    def __init__(self, *options):
        self.options = options

class Atom(CombModel):
    def __iter__(self):
        for x in self.options:
            yield x

class All(CombModel):
    def __iter__(self):
        for prod in itertools.product(*self.options):
            yield prod

class One(CombModel):
    def __iter__(self):
        for x in self.options:
            for y in x:
                yield y

class Mix(CombModel):
    def __iter__(self):
        for n in range(len(self.options) + 1):
            for perm in itertools.permutations(self.options, n):
                for prod in itertools.product(*perm):
                    yield prod

CombModel 只为所有子类提供一个可变参数构造函数。 Atom 是模型中的一片“叶子”，它的存在使我甚至可以“迭代”单个字符串或整数。这会在所有其他类中保存一些 if/else 逻辑。 All 在您的模型中似乎是普通列表，产生不同选项的乘积。 One 和 Mix 对应于你的 PickOne 和 Mix。

使用这个相当简单的模型 comb = Mix(All(Atom(1), Atom(21, 22)), One(Atom(31, 32), Atom(4))) I得到这些组合:

()
((1, 21),)
((1, 22),)
(31,)
(32,)
(4,)
((1, 21), 31)
((1, 21), 32)
((1, 21), 4)
((1, 22), 31)
((1, 22), 32)
((1, 22), 4)
(31, (1, 21))
(31, (1, 22))
(32, (1, 21))
(32, (1, 22))
(4, (1, 21))
(4, (1, 22))

您的模型转换为:

model = Mix(
    All(
        Atom("this"),
        One(Atom("is"), Atom("isn't"))
    ),
    One(
        Mix(
            Atom("absolutely"),
            Atom("great")
        )
    )
)

并给出这些组合:

()
(('this', 'is'),)
(('this', "isn't"),)
((),)
(('absolutely',),)
(('great',),)
(('absolutely', 'great'),)
(('great', 'absolutely'),)
(('this', 'is'), ())
(('this', 'is'), ('absolutely',))
(('this', 'is'), ('great',))
(('this', 'is'), ('absolutely', 'great'))
(('this', 'is'), ('great', 'absolutely'))
(('this', "isn't"), ())
(('this', "isn't"), ('absolutely',))
(('this', "isn't"), ('great',))
(('this', "isn't"), ('absolutely', 'great'))
(('this', "isn't"), ('great', 'absolutely'))
((), ('this', 'is'))
((), ('this', "isn't"))
(('absolutely',), ('this', 'is'))
(('absolutely',), ('this', "isn't"))
(('great',), ('this', 'is'))
(('great',), ('this', "isn't"))
(('absolutely', 'great'), ('this', 'is'))
(('absolutely', 'great'), ('this', "isn't"))
(('great', 'absolutely'), ('this', 'is'))
(('great', 'absolutely'), ('this', "isn't"))

请注意，这些仍然是嵌套列表(实际上是元组)，但它们很容易是 flattened然后。此外，由于 Mix 的“零个或多个”性质，还有一些伪重复项(在展平时会重复)。但除此之外，这看起来非常接近您的预期输出。

---

仔细观察，可能确实需要先展平，这样 PickOne 才会从 Mix 中选择一个而不是整个 Mix...

class All(CombModel):
    def __iter__(self):
        for prod in itertools.product(*self.options):
            yield flat(prod) # flatten here

class One(CombModel):
    def __iter__(self):
        for x in self.options:
            for y in flat(x): # flatten here
                yield y

class Mix(CombModel):
    def __iter__(self):
        for n in range(len(self.options) + 1):
            for perm in itertools.permutations(self.options, n):
                for prod in itertools.product(*perm):
                    yield flat(prod) # flatten here

剔除重复后的结果是这样的:

()
('absolutely',)
('absolutely', 'this', 'is')
('absolutely', 'this', "isn't")
('great',)
('great', 'this', 'is')
('great', 'this', "isn't")
('this', 'is')
('this', 'is', 'absolutely')
('this', 'is', 'great')
('this', "isn't")
('this', "isn't", 'absolutely')
('this', "isn't", 'great')