Python长排列与重复字符

Question

Python长排列与重复字符

5

我正在尝试生成类似于“0000011111”或“000 11 2222 333”这样的字符串的所有可能排列。我尝试使用itertools中的permutations对“0000011111”进行操作，如下所示：

from itertools import permutations

basestring = "0"*5 +"1"*5 
perms = [''.join(p) for p in permutations(basestring)]
print(len(perms), perms)
print(len(set(perms)), set(perms))

但是当排列只有10个C5 = 252种时，列表perms却有300万个条目。

是否有内置工具可以更好地处理具有许多重复字符的字符串的排列？

否则，如何使用此算法生成排列（对于“0000 1111 222”）？

Start with 2 characters        "0000 1111"
Move right most 0 over one     "0001 0111" and add it to the list
Continue moving it to the end  "0001 1011" -> "0001 1101" -> "0001 1110"

Now move the next 0 over one   "0010 0111" -> "0010 1011"
...
Until you get to "1111 0000".

Then for each of the strings generated, repeat the process with 2's.
222 xxxx xxxx -> 22x 2xxx xxxx -> 22x x2xx xxx...

我是不是最好只做set(perms)来去除重复项？（我需要排列由3-5个字符组成的20个字符列表，其中itertools permutations会给我10e18个字符串）

我已经业余编程三年了，但只知道与一个学期的编程课程相当的知识。

- Frank Noam

3

请看这个问题，看看其中的答案是否有帮助。 - Rusty Shackleford

2

你对自己想要做的事情的解释不太清晰。你说你正在寻找排列（nPr），但是你给出了组合数（nCr）的计算方法。你使用“字符串”这个术语时可能意思是“列表”，尽管在Python中，字符串实际上是字符列表并且可迭代。看起来你对自己所寻求的有一个清晰的想法，请尽量不让我们猜测。 - msw

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- גלעד ברקן · Answer 1

我不确定这个方法的效率如何，但你可以尝试类似这样的代码：

map = ['0','1','2','3']
perms = []

def multisetPerms(s,result):
  if all(v is 0 for v in s):
    perms.append(result)
    return
  for i in xrange(len(s)):
    if s[i] > 0:
      _s = s[:]
      _s[i] = _s[i] - 1
      multisetPerms(_s,result + map[i])

multisetPerms([3,2,4],'') # 9!/(3!*2!*4!) = 1260
print (len(perms), perms[0:10])

输出：

(1260, ['000112222', '000121222', '000122122', '000122212', '000122221'
      , '000211222', '000212122', '000212212', '000212221', '000221122'])

- paisanco · Answer 2

首先让我们看一下你的第一个例子。

from itertools import permutations
basestring = "0"*5 +"1"*5

这将给出basestring = [0000011111]

如果不带任何参数调用permutations(basestring)，将会得到长度为n的n位置字符串的所有排列，即n! 对于n=10来说，这确实是一个很大的数字。这真的是你想要的吗？

接下来，如果你正在寻找长度为5的该字符串的排列，你需要在调用itertools.permutations时指定该长度为5。

perms = [''.join(p) for p in permutations(basestring,5)]

这将按位置返回basestring中所有字符的长度为5的所有排列，而不是值。因此，您将获得一些重复项。

正如在itertools.permutations文档（请参见Python 2版本）中记录的那样，该函数返回长度为n的字符串上长度为r的排列数将是

n!/(n-r)!，在这种情况下为30240，其中n=10，r=5。

如果要删除重复项，则可以执行以下操作

set(perms)

这个函数返回的组合数量将是 len(set(perms)) = 2^5 或者 32。这是从长度为 k 的“字母表”中可以形成的字符串数量，该“字母表”的长度为 n，即 n^k。在你的基础字符串中，唯一的字符就是“字母表” - 这里有两个字符（0和1），所以你可以从中形成32个长度为5的独特字符串。