計算字符串的排列

我需要問題的幫助。給定一個帶有重複的輸入字符串，比如說「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

計算字符串的排列

回答

相關問題