+ -r，+-s的所有排列 [英] all permutations of +-r, +-s

问题描述

给出两个数字 r 和 s ，我想获取所有<$ c排列的列表$ c> n +-r 和 m +- s 。例如（使用 r = 3.14 和 s = 2.71 ），

Given two numbers r and s, I would like to get a list of all permutations of n +-r and m +-s. For example (with 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), ...
    ...
    ]

使用 itertools.product（[+ r，-r]，repeat = n）分别获取 r s和 s s的列表，我只需要缠绕它们即可，但是我我不确定这样做是否正确。

With itertools.product([+r, -r], repeat=n) I can get the list of the rs and ss separately, and I'd only need to intertwine them, but I'm not sure if this is the right thing to do.

效率并不是太重要，所以我不介意产生很多重复结果的解决方案

Efficiency is not overly important, so I wouldn't mind a solution that produces many repeated results only to make them unique afterwards.

推荐答案

更新：已添加常规解决方案。

Update: general solution added.

这里的解决方案在代码上更加复杂，但是不会产生重复的元素，因此可以懒惰地求值：

Here is a solution that is bit more complicated in code but does not produce repeated elements and can be evaluated lazily:

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)

说明

我们可以将输出视为包含<$ c $的排列c> n +/- r 个元素和 m +/- s 个元素，换句话说就是 n + m 个元素的元组其中 n 为+/- r ，其余为+/- s 。 idx 包含具有+/- r 元素的所有可能位置的元组；例如，对于第一个结果，它是（0，）。

We can think of the output as permutations containing n +/- r elements and m +/- s elements, or, in other words, tuples of n + m elements where n are +/- r and the rest are +/- s. idx contains tuples with all the possible positions for +/- r elements; for example, for the first result it is (0,).

然后，对于每个元组 i 我们在 vs 中创建模板元组，它们只是大小为 n 的元组code> + m 其中， i 中的索引为 r ，其余为 s 。因此，对于 idx 中的元组（0，），您将得到（r，s ，s）。如果 n + m 很大，则可以考虑上一步 idx = map（set ，idx）来实现更快的 操作，但是我不确定在哪一点值得。

Then, for each of these tuples i we create "template" tuples in vs, which are just tuples of size n + m where indices in i are r and the rest are s. So, for the tuple (0,) in idx you would get (r, s, s). If n + m is very big you could consider a previous step idx = map(set, idx) for a faster in operation, but I'm not sure at which point that would be worth it.

最后，对于 v 中的每个模板 vi 对每个元素使用正值和负值的可能性。因此它是（+ vi [0]，-vi [0]），（+ vi [1]，-vi [1]），... 。最后，您只需要链接这些产品的每个生成器，即可获得最终结果。

Finally, for each of these templates vi in v I need to consider all the possibilities using a positive and negative value for each of its elements. So it is a Cartesian product of (+vi[0], -vi[0]), (+vi[1], -vi[1]), .... And finally you just need to chain each of the generator of each of these products to get the final result.

常规解决方案

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

To build a general solution to the problem for an arbitrary number of different elements, you need to consider partitions of the set of indices. For example, for n = 3 and m = 5, all the possible ways you can split {0, 1, 2, 3, 4, 5, 6, 7} in two parts of sizes 3 and 5. Here is an implementation for that:

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

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

The idea is the same, you build the "templates" (this time they contain indices of the values instead of the values themselves) and then the Cartesian products from them.

这篇关于+ -r，+-s的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！