的所有排列+ -R，+ -s

鑑於兩個數字r和s，我想獲得的n+-r和m+-s所有排列的列表。例如（與r=3.14和s=2.71），的所有排列+ -R，+ -s

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小號分開，而我只需要糾結他們，但我不確定這是否是正確的做法。

效率不是非常重要，所以我不介意一個解決方案產生許多重複的結果只是爲了使它們以後獨一無二。

來源

2017-07-26 Nico Schlömer

更新：添加了一般解決方案。

這裏是一個解決方案，是比較複雜一點在代碼，但不會產生重複的元素，並且可以懶惰地評估：

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 +/- re的排列lements和m +/- s元件，或者，換句話說，的n + m元素，其中n是+/- r，其餘元組是+/- s。 idx包含具有+/- r元素的所有可能位置的元組;例如，第一個結果是(0,)。

然後，對每個這些元組i我們創造vs「模板」的元組，這只是大小的元組n + m其中i指數r，其餘爲s。因此，對於idx中的元組(0,)，您將獲得(r, s, s)。如果n + m是非常大的，你可以考慮前面的步驟idx = map(set, idx)一個更快in操作，但我不知道在這一點，將是值得的。

最後，對於這些模板中的每一個vi在v我需要考慮所有可能性，爲它的每個元素使用正值和負值。所以它是(+vi[0], -vi[0]), (+vi[1], -vi[1]), ...的笛卡爾積。最後，你只需要鏈接每個這些產品的每一個發電機來獲得最終結果。

通用的解決方案

要建立不同的元素任意數量的問題的通用解決方案，你需要考慮分區索引集的。例如，對於n = 3和m = 5，所有可能的方式，你可以在尺寸3和5這裏分爲兩個部分{0, 1, 2, 3, 4, 5, 6, 7}是一個實現：

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

的想法是一樣的，你建的「模板「（這次他們包含價值指數而不是價值本身），然後是笛卡爾產品。

來源

2017-07-26 08:51:42 jdehesa

這似乎不工作：'list（itertools.product（*（[[+ r，-r]] * 1 + [[ （3.14，2.71），（3.14，-2.71），（-3.14，2.71），（-3.14，-2.71）]' - '3.14'從來沒有排在第二位。 –

@NicoSchlömerOhh對不起，我誤讀了您的示例輸出 – jdehesa

一兩個解釋無疑有助於理解代碼。 –

首先使用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)

來源

2017-07-26 09:02:13 Arseniy

你也可以用+1的product和-1和zip兩者結合的r和s的permutations。這樣，整個結構是更可讀一些恕我直言：

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

來源

2017-07-26 09:23:21

的所有排列+ -R，+ -s

回答

相關問題