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

给定两个数字r and s，我想获得所有排列的列表n +-r and m +-s。例如（与r=3.14 and 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), ...
    ...
    ]

With itertools.product([+r, -r], repeat=n)我可以得到名单rs and s是分开的，我只需要将它们交织在一起，但我不确定这是否是正确的做法。

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

Update:添加了通用解决方案。

这是一个代码稍微复杂一些但不会产生重复元素并且可以延迟计算的解决方案：

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)))

Output:

(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，它们只是大小的元组n + m其中索引i are r其余的是s。所以，对于元组(0,) in idx你会得到(r, s, s). If n + m非常大，您可以考虑上一步idx = map(set, idx)为了更快in操作，但我不确定在什么时候这是值得的。

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

通用解决方案

要为任意数量的不同元素构建问题的通用解决方案，您需要考虑分区的索引集。例如，对于n = 3 and 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)))

想法是相同的，您构建“模板”（这次它们包含值的索引而不是值本身），然后从中构建笛卡尔积。