计算字符串的排列

我需要问题的帮助。给定一个带有重复的输入字符串，比如说“aab”，如何计算该字符串的不同排列的数量。可以使用的一个公式是n！/ n1！n2！..... nr !.计算字符串的排列

然而，计算这些ni需要时间O（rn）和O（n），如果我们使用查找表。

但是，我需要一个解决方案，而不使用这种tables.Is任何递归或动态编程解决方案可能出现此问题。

在此先感谢。

来源

2011-06-12 Shrinu Kushagra

不应该是简单的n！（如果n是你的字符串的长度）？ – MRalwasser 2011-06-12 10:38:46

@MRalwasser：这只有在所有角色都不同时才有效。当重复字符被允许时，OP的公式是正确的。例如，''aaa“'有1个不同的排列，而不是3 !. – hammar 2011-06-12 10:43:53

我相信递归或动态编程解决方案将比这个查找表占用更多的空间，其长度可以由字母大小和字符串长度的最小值来限定。唯一的建议是尽快取消分子和分母的共同因素。 – 2011-06-12 10:51:30

-1

正如@MRalwasser所说，排列的数量应该是n！你可以相当简单地排列generate those，但运行时间将呈指数形式，因为你必须按指数规律来命中许多输出字符串。（快捷方式来表明O（ñ！）= 0（2 ^ñ）是利用Stirling's Formula）

来源

2011-06-12 10:43:18

我们只计算不同的排列，例如字符串“aab”只有三个（“aab”，“aba”，“baa”），而不是6 – marnir 2011-06-12 10:46:56

然后你应该清楚地说明你在重复输入字符串。我编辑了这个问题。 – 2011-06-12 10:51:44

斯特林的逼近比O（2^n）多O（n^n） - 给定一个有限的字符集，然而，你的确限于指数多数。 – 2011-06-12 10:58:04

如果你想为非常大的字符串做到这一点，可以考虑使用伽玛函数（伽马（ n + 1）= n！），这对于大n来说更快，并且即使在出现int溢出的情况下，仍然可以提供浮点精度。

如果您有任意的精度算术，您可以通过利用您可以（例如，（1 * 2 * 3）^ 3 * 4^2 * 6 * 7写入1 * 2 * 3 * 1 * 2 * 3 * 4 * 1 * 2 * 3 * 4 * 5 * 6 * 7。最终结果仍然会有O（rn）个数字，并且您仍然需要O（rn）时间消耗，因为乘积成本会随着数字的大小而增加。

我没有看到查找表和动态编程之间的区别 - 基本上，动态编程使用您在运行中建立的查找表。（即，使用查找表，但仅按需填充）。

来源

2011-06-12 11:09:34

你需要近似的答案或确切的答案吗？你认为这个计算的哪一部分很慢？

如果您需要近似的答案，请使用@Yannick Versley建议的伽玛函数。

如果你需要确切的答案，这里是我该怎么做。我首先找出答案的主要因式分解，然后将这些因子相乘。这避免了分裂。计算主分解的难点在于找出n!的主分解。为此，你可以使用一个技巧。假设p是素数，并且k是n/p'. Then the number of times that的整数部分pdividesn！ is k plus the number of times that p divides k 80！ is 26 + 8 + 2 = 36`。因此，在找到'n'的质数后，不难发现'n！'的质数因子分解。

一旦你知道了素因子分解，你可以乘以它。你希望处理大量的数据，所以尽量安排先做很多小的乘法运算，然后再安排一些大的乘法运算。这是一个简单的方法来做到这一点。

制作一系列主要因素。争夺它（混合大小因素）。然后只要你的阵列中至少有2个因素抓住前两个因素，把它们相乘，推到最后。当你剩下一个号码时，这就是你的答案。

对于大字符串，这应该比一次乘以一个数字的天真方法快得多。但最后你会有非常多的数字，没有什么可以让这些快速增长。

来源

2011-06-12 19:05:26 btilly

没有。的不同的置换是n!/(c1!*c2*..*cn!) 这里n是字符串

ck的长度表示没有。每个独特人物的发生。

对于如：字符串：AABB N = 4 CA = 2，CB = 2
液= 4/= 6

来源

2013-09-21 08:22:15 user29

你可以保持运行计数！（2 * 2！）为每个角色，并随着你的进展而建立结果。不可能比O（n）做得更好，因为如果不查看字符串中的每个字符，都无法知道每个字符有多少。

我已经用Python编写了一些代码，并进行了一些简单的单元测试。代码在结果很小时会小心避免大的中间值（事实上，变量result永远不会比len（s）乘以最终结果大）。如果你要用另一种语言编写代码，比如说C，那么你可以使用一个256而不是defaultdict的数组。

如果你想要一个确切的结果，那么我认为你可以做得比这更好。

from collections import defaultdict 

def permutations(s): 
    seen = defaultdict(int) 
    for c in s: 
     seen[c] += 1 
    result = 1 
    n = 0 
    for k, count in seen.iteritems(): 
     for j in xrange(count): 
      n += 1 
      result *= n 
      result //= j + 1 
    return result 

test_cases = [ 
    ('abc', 6), 
    ('aab', 3), 
    ('abcd', 24), 
    ('aabb', 6), 
    ('aaaaa', 1), 
    ('a', 1)] 
for s, want in test_cases: 
    got = permutations(s) 
    if got != want: 
     print 'permutations(%s) = %s want %s' % (s, got, want)

来源

2013-09-21 08:41:21

计算字符串的排列

回答

相关问题