+-r, +-s 的所有排列

Question

给定两个数字 r 和 s，我想得到 n +-r 和 m [=17] 的所有排列的列表=].例如（r=3.14 和 s=2.71），

n = 1
m = 1
out = [
    (+r, +s), (+r, -s), (-r, +s), (-r, -s), 
    (+s, +r), (+s, -r), (-s, +r), (-s, -r)
    ]

n = 1
m = 2
out = [
    (+r, +s, +s), (+r, -s, +s), (-r, +s, +s), (-r, -s, +s), ...
    (+s, +r, +s), (-s, +r, +s), (+s, -r, +s), (-s, -r, +s), ...
    ...
    ]

使用itertools.product([+r, -r], repeat=n)我可以分别得到r和s的列表，我只需要将它们交织在一起，但我不确定是否这是正确的做法。

效率并不过分重要，所以我不介意产生许多重复结果只是为了让它们在之后变得独一无二的解决方案。

Answer 1

更新： 添加了通用解决方案。

这里有一个解决方案，代码有点复杂，但不会产生重复的元素，可以延迟计算：

from itertools import combinations, product, chain

r = 3.14
s = 2.71
n = 1
m = 2
idx = combinations(range(n + m), n)
vs = ((r if j in i else s for j in range(n + m)) for i in idx)
res = chain.from_iterable(product(*((+vij, -vij) for vij in vi)) for vi in vs)
print("\n".join(map(str, res)))

输出：

(3.14, 2.71, 2.71)
(3.14, 2.71, -2.71)
(3.14, -2.71, 2.71)
(3.14, -2.71, -2.71)
(-3.14, 2.71, 2.71)
(-3.14, 2.71, -2.71)
(-3.14, -2.71, 2.71)
(-3.14, -2.71, -2.71)
(2.71, 3.14, 2.71)
(2.71, 3.14, -2.71)
(2.71, -3.14, 2.71)
(2.71, -3.14, -2.71)
(-2.71, 3.14, 2.71)
(-2.71, 3.14, -2.71)
(-2.71, -3.14, 2.71)
(-2.71, -3.14, -2.71)
(2.71, 2.71, 3.14)
(2.71, 2.71, -3.14)
(2.71, -2.71, 3.14)
(2.71, -2.71, -3.14)
(-2.71, 2.71, 3.14)
(-2.71, 2.71, -3.14)
(-2.71, -2.71, 3.14)
(-2.71, -2.71, -3.14)

说明

我们可以将输出视为包含 n +/- r 元素和 m +/- s 元素的排列，或者换句话说， n + m 元素的元组，其中 n 是 +/- r，其余是 +/- s。 idx 包含具有 +/- r 元素所有可能位置的元组；例如，第一个结果是 (0,).

然后，对于这些元组中的每一个 i，我们在 vs 中创建 "template" 个元组，它们只是大小为 n + m 的元组，其中i 中的索引是 r，其余是 s。因此，对于 idx 中的元组 (0,)，您将得到 (r, s, s)。如果 n + m 非常大，您可以考虑上一步 idx = map(set, idx) 以获得更快的 in 操作，但我不确定在哪一点上值得.

最后，对于 v 中的每个模板 vi，我需要考虑所有的可能性，为其每个元素使用正值和负值。所以它是 (+vi[0], -vi[0]), (+vi[1], -vi[1]), ... 的笛卡尔积。最后，您只需将这些产品的每个生成器链接起来即可获得最终结果。

一般解

要针对任意数量的不同元素构建问题的通用解决方案，您需要考虑索引集的 partitions。例如，对于 n = 3 和 m = 5，您可以将 {0, 1, 2, 3, 4, 5, 6, 7} 分成大小为 3 和 5 的两部分的所有可能方式。这是一个实现：

from itertools import chain, repeat, permutations, product


def partitions(*sizes):
    if not sizes or all(s <= 0 for s in sizes):
        yield ()
    for i_size, size in enumerate(sizes):
        if size <= 0:
            continue
        next_sizes = sizes[:i_size] + (sizes[i_size] - 1,) + sizes[i_size + 1:]
        for p in partitions(*next_sizes):
            yield (i_size,) + p


def signed_permutations(*elems):
    values, sizes = zip(*elems)
    templates = partitions(*sizes)
    return chain.from_iterable(
        product(*((+values[ti], -values[ti]) for ti in t)) for t in templates)


r = 3.14
s = 2.71
n = 1
m = 2
res = signed_permutations((r, n), (s, m))
print("\n".join(map(str, res)))

想法是一样的，您构建 "templates"（这次它们包含值的索引而不是值本身），然后从中构建笛卡尔积。

Answer 2

首先对每个元素使用 product，然后使用 permutations。然后连接所有结果并将它们传递给 set() 以删除重复项：

arr = set(itertools.chain.from_iterable([
    itertools.permutations(x)
    for x in itertools.product(*([[+r, -r]] * n + [[+s, -s]] * m))
    ]))
print(arr)

Answer 3

您还可以将 r 和 s 的 permutations 与 +1 和 -1 和 [=17 的 product 结合起来=] 两个。这样，整个结构更具可读性恕我直言：

>>> n, m = 1, 2
>>> r, s = 3.14, 2.71
>>> [[x*i for x,i in zip(perm, prod)] for perm in permutations([r]*n + [s]*m) 
...                                   for prod in product((+1, -1), repeat=n+m)]
[[3.14, 2.71, 2.71],
 [3.14, 2.71, -2.71],
 ...
 [-2.71, -2.71, 3.14],
 [-2.71, -2.71, -3.14]]

+-r, +-s 的所有排列

all permutations of +-r, +-s

python

combinatorics

itertools