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

Question

鉴于两个数字r和s,我想获得的所有排列的列表n +-r和m +-s.例如(带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)我可以得到的名单rS和s单独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,它们只是大小的元组n+ m其中的索引i是r,其余的是s.因此,对于元组(0,)中idx,你会得到(r, s, s).如果n+ m非常大,你可以考虑采用前一步骤idx = map(set, idx)来加快in操作速度,但我不确定哪一点值得.

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

一般解决方案

要为任意数量的不同元素构建问题的一般解决方案,您需要考虑索引集的分区.例如,for 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)))

这个想法是一样的,你构建"模板"(这次它们包含值的索引而不是值本身),然后是它们的笛卡尔积.

Answer 2

你也可以结合permutations的r,并s与product中+1和-1及zip两个.这样,整个构造更具有可读性恕我直言:

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