使用itertools获得大量唯一排列 [英] Using itertools to get a large number of unique permutations

问题描述

我有这样一个问题:有多少种方法可以改变鳄梨汁"中字母的顺序，从而使元音首先出现，例如"ovacadojuice"是一种解决方案?起点-鳄梨汁"也是一种解决方案. 我知道itertools.permutations可以做这样的事情，但是如果单词太长，则会弹出内存错误.有什么方法可以防止这种情况，或者有另一个内置模块可以解决此问题?先感谢您！ P.S.我知道如何将置换元组转换为字符串.

I have a question as such: How many ways are there to change order of letters in "avocadojuice" so that the vowel comes up first, for example "ovacadojuice" is a solution? The starting point - "avocadojuice" is also a solution. I know that itertools.permutations can do things like this, but if the word is too long it pops up a memory error. Is there a way to prevent this, or maybe there is another built in module, which can solve this? Thank you in advance! P.S. I know how to turn permutation tuples into strings.

推荐答案

在这种情况下，暴力破解问题可能不可行.您需要计算 n 个元素的唯一排列的数量，这要考虑到某些元素被重复的事实.

This is a case were brute-forcing the problem probably isn't feasible. You need to compute the number of unique permutations of n elements, accounting for the fact that some elements are repeated.

对此有一个数学公式，并且一些 答案在其他堆栈交换站点上.

There is a mathematical formula for this, and some excellent answers on other stack exchange sites.

仅重复a和o，所以avocadojuice的唯一置换数为

Only a and o are repeated, so the number of unique permuations of avocadojuice is

(12!) / (2!2!)

或119750400

每个12个字符的字符串大约为45 bytes(至少在我的机器上)，超过5兆的内存仅用于存储近1.2亿个排列！您可以看到为什么强行强制执行此操作不是一个好主意.

At roughly 45 bytes per 12-character string (on my machine at least), that's over 5 gigs of memory just to store the nearly 120 million permutations! You can see why brute forcing this isn't such a great idea.

但是，您在问题中还有一个额外的要求，即排列必须以元音开头.假设只有5个元音，您应该能够将每个给定的元音作为第一个字符来计算可能的排列.

You have one extra requirement in your problem though, which is that the permutations must start with a vowel. Given that there are only 5 vowels, you should be able to calculate the possible permutations with each of the given vowels as the first character.

(11! / 2!) +      # a (only o is repeated)
(11! / (2!2!)) +  # e
(11! / (2!2!)) +  # i
(11! / 2!) +      # o (only a is repeated)
(11! / (2!2!)) +  # u

这篇关于使用itertools获得大量唯一排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！