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

用python中的重复生成排列

combinatorics permutation python

Bwmat · 技术社区 · 14 年前

我知道Itertools,但它似乎只能生成排列而不需要重复。

例如,我想为2个骰子生成所有可能的骰子卷。所以我需要所有2号的排列,包括重复:(1,1),(1,2),(2,1)。等

如果可能的话,我不想从头开始实施

5 回复 | 直到 8 年前

miku 9 年前

你在找 Cartesian Product .

在数学中,笛卡尔积(或积集)是两个集的直积。

在你的情况下,这是 {1, 2, 3, 4, 5, 6} X _1、2、3、4、5、6_ . itertools 可以帮助您:

import itertools
x = [1, 2, 3, 4, 5, 6]
[p for p in itertools.product(x, repeat=2)]
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), 
 (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), 
 (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), 
 (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]

要得到一个随机的骰子掷骰子(以一种完全无效的方式):

import random
random.choice([p for p in itertools.product(x, repeat=2)])
(6, 3)

Mark Byers 14 年前

你不是在找排列-你想要 Cartesian Product . 用于此用途 product 从迭代工具:

from itertools import product
for roll in product([1, 2, 3, 4, 5, 6], repeat = 2):
    print(roll)

SilentGhost 14 年前

在python 2.7和3.1中有一个 itertools.combinations_with_replacement 功能:

>>> list(itertools.combinations_with_replacement([1, 2, 3, 4, 5, 6], 2))
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 3), (2, 4), 
 (2, 5), (2, 6), (3, 3), (3, 4), (3, 5), (3, 6), (4, 4), (4, 5), (4, 6),
 (5, 5), (5, 6), (6, 6)]

Eric_HL_DoCode 8 年前

首先,您要先将itertools.permutations(list)返回的生成器转换为一个列表。其次,可以使用set()删除重复项如下所示:

def permutate(a_list):
    import itertools
    return set(list(itertools.permutations(a_list)))

-4

NNP 10 年前

这里是C版本(尽管它要求使用python,但算法应该相同),仅供参考:

下面的方法基本上需要掷骰子的次数才能得到各种排列。对于上述问题,大小应为“2”。

private void GetAllPermutationsOfDice_Recursive(int size, string currentValue, 
            List<string> values)
        {
            if(currentValue.Length == size)
            {
                values.Add(currentValue);
                return;
            }
            for(int i = 1; i<=6;i++)
            {
                this.GetAllPermutationsOfDice_Recursive(size, currentValue + i, values);   
            }
        }

要掷两次骰子,上述方法可以调用为:

public string[] GetAllPermutationsOfDiceOfSize_2()
        {
            List<string> values = new List<string>();
            this.GetAllPermutationsOfDice_Recursive(2, "", values);
            return values.ToArray();
        }

以下是相应的单元测试:

[TestMethod]
        public void Dice_PermutationsTests()
        {
            var v = this.GetAllPermutationsOfDiceOfSize_2();
            Assert.AreEqual(36, v.Length);
            int l = 6;
            List<string> values = new List<string>();
            for(int i = 1; i<=4; i++)
            {
                values.Clear();
                this.GetAllPermutationsOfDice_Recursive(i, "", values);
                Assert.AreEqual(l, values.Count);
                l *= 6;
            }
        }