代码之家 › 专栏 › 技术社区 › kPow989

生成唯一置换的Itertools函数

itertools permutation python

kPow989 · 技术社区 · 9 年前

itertools 产生以下组合/置换的方法:

list = ['x', 'o']

# when character 'x' is allowed to occupy 1 place with total places of 4:

a = [['o','o','o','x'],
     ['o','o','x','o'],
     ['o','x','o','o'],
     ['x','o','o','o']]

# when character 'x' is allowed to occupy 2 places with total places of 4:

b = [['o','o','x','x'],
     ['o','x','x','o'],
     ['x','x','o','o'],
     ['x','o','x','o'],
     ['o','x','o','x'],
     ['x','o','o','x']]

我想知道是否有一种方法可以使用 itertools.product 或者类似的功能来实现这一点?

2 回复 | 直到 9 年前

Vinícius Figueiredo 9 年前

itertools.permutations 也接受字符串作为参数:

from itertools import permutations
>>> list(permutations("ooox"))
[('o', 'o', 'o', 'x'), ('o', 'o', 'x', 'o'), ('o', 'o', 'o', 'x'), ('o', 'o', 'x', 'o'), ('o', 'x', 'o', 'o'), ('o', 'x', 'o', 'o'), ('o', 'o', 'o', 'x'), ('o', 'o', 'x', 'o'), ('o', 'o', 'o', 'x'), ('o', 'o', 'x', 'o'), ('o', 'x', 'o', 'o'), ('o', 'x', 'o', 'o'), ('o', 'o', 'o', 'x'), ('o', 'o', 'x', 'o'), ('o', 'o', 'o', 'x'), ('o', 'o', 'x', 'o'), ('o', 'x', 'o', 'o'), ('o', 'x', 'o', 'o'), ('x', 'o', 'o', 'o'), ('x', 'o', 'o', 'o'), ('x', 'o', 'o', 'o'), ('x', 'o', 'o', 'o'), ('x', 'o', 'o', 'o'), ('x', 'o', 'o', 'o')]

和

>>> list(permutations("ooxx"))
[('o', 'o', 'x', 'x'), ('o', 'o', 'x', 'x'), ('o', 'x', 'o', 'x'), ('o', 'x', 'x', 'o'), ('o', 'x', 'o', 'x'), ('o', 'x', 'x', 'o'), ('o', 'o', 'x', 'x'), ('o', 'o', 'x', 'x'), ('o', 'x', 'o', 'x'), ('o', 'x', 'x', 'o'), ('o', 'x', 'o', 'x'), ('o', 'x', 'x', 'o'), ('x', 'o', 'o', 'x'), ('x', 'o', 'x', 'o'), ('x', 'o', 'o', 'x'), ('x', 'o', 'x', 'o'), ('x', 'x', 'o', 'o'), ('x', 'x', 'o', 'o'), ('x', 'o', 'o', 'x'), ('x', 'o', 'x', 'o'), ('x', 'o', 'o', 'x'), ('x', 'o', 'x', 'o'), ('x', 'x', 'o', 'o'), ('x', 'x', 'o', 'o')]

要将它们存储在问题中所示的列表中,您可以使用 map(list, permutations("ooox"))

正如您在注释部分中提到的,我们可以为该作业编写一个特定的函数,该函数接受您想要的输入,但请注意,当第一个字符串的长度不是1时,这将以一种不太理想的方式运行:

from itertools import permutations
def iterate(lst, length, places):
    return set(permutations(lst[0]*(length-places)+lst[1]*places))

演示:

>>> from pprint import pprint
>>> pprint(iterate(["o","x"], 4, 1))
{('o', 'o', 'o', 'x'),
 ('o', 'o', 'x', 'o'),
 ('o', 'x', 'o', 'o'),
 ('x', 'o', 'o', 'o')}
>>> pprint(iterate(["o","x"], 4, 2))
{('o', 'o', 'x', 'x'),
 ('o', 'x', 'o', 'x'),
 ('o', 'x', 'x', 'o'),
 ('x', 'o', 'o', 'x'),
 ('x', 'o', 'x', 'o'),
 ('x', 'x', 'o', 'o')}

MSeifert 9 年前

itertools.combinations :

from itertools import combinations

def equivalence_permutations(x, o):
    """Create all unique permutations with `x` x'es and `o` o's."""
    total = x+o
    for indices in combinations(range(total), x):
        lst = ['o']*total
        for index in indices:
            lst[index] = 'x'
        yield lst

这个 combinations 确保索引是唯一的,无需使用 set 或任何其他贪婪的操作。因此,在这些情况下,速度应该快得多。例如:

>>> list(equivalence_permutations(2, 2))  # 2 x and 2 o
[['x', 'x', 'o', 'o'],
 ['x', 'o', 'x', 'o'],
 ['x', 'o', 'o', 'x'],
 ['o', 'x', 'x', 'o'],
 ['o', 'x', 'o', 'x'],
 ['o', 'o', 'x', 'x']]

>>> list(equivalence_permutations(1, 3))  # 1 x and 3 o
[['x', 'o', 'o', 'o'],
 ['o', 'x', 'o', 'o'],
 ['o', 'o', 'x', 'o'],
 ['o', 'o', 'o', 'x']]