来自模型的嵌套排列

Question

我正在编写一个程序，它接受字符串的排列 "model"，并根据该模型输出所有排列。该模型看起来像这样：

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

在输出的排列中，

list个对象会依次输出包含的对象
Mix objects 将以各种可能的顺序输出包含的对象，最大长度（包括零）
PickOne个对象一次只会输出一个包含它的对象

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

[
    ["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 的排列，如下所示：

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)

我的PickOneclass就是这样

class PickOne(list):
    pass

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

itertools 为更简单的用例提供了简化和效率，但是我不知道它将如何帮助我实现这个实现（除了我已经在 Mix 中实现的）。关于如何使用 itertools 来帮助以 Pythonic 方式实现上述内容，有什么想法吗？

Answer 1

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

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 只为所有子class 提供了一个可变参数构造函数。 Atom 是模型中的 "leaf" 并且它在那里，所以我可以 "iterate" 甚至在单个字符串或整数上。这在所有其他 class 中节省了一些 if/else 逻辑。 All 在您的模型中似乎是普通列表，产生不同选项的乘积。 One和Mix对应你的PickOne和Mix.

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

()
((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 的 "zero or more" 性质，存在一些伪重复项（在展平时会重复）。但除此之外，这看起来非常接近您的预期输出。

仔细观察，可能确实需要先展平，这样 PickOne 将 select 只有一个来自 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')

来自模型的嵌套排列

Nested Permutations from Model

python

algorithm

permutation

combinatorics

itertools