如何使用更少的內存生成Array排列？

Question

所以我需要得到一個字符串的所有可能的排列。

我現在是這樣的：

def uniq_permutations string 
    string.split(//).permutation.map(&:join).uniq 
end 

好了，現在什麼是我的問題：這種方法適用於小串，但我希望能夠與類似的15尺寸用繩子用它甚至可能是20個。使用這種方法它使用了大量的內存（> 1GB），我的問題是我可以改變不使用那麼多的內存？

有沒有更好的方法來產生排列？我應該堅持他們在文件系統和檢索時，我需要他們（我希望不是因爲這可能會使我的方法變慢）？

我能做些什麼？

更新：

我其實並不需要保存結果的任何地方我只需要查找每個表中的，看它是否存在。

Answer 1

只是爲了重申薩瓦說。你確實瞭解範圍？任何n元素的排列數是n!。這是關於您可以獲得的最積極的數學進展操作。對於n 1-20之間的結果是：

[1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 
6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 
6402373705728000, 121645100408832000, 2432902008176640000] 

當最後一個數字是大約2百萬的三次方，也就是2十億十億。

即2265820000千兆字節。

你可以整天將結果保存到磁盤 - 除非你自己在世界上所有的谷歌的數據中心你會是相當多的運氣在這裏:)

Answer 2

也許我缺少明顯的，但爲什麼不

['a','a','b'].permutation.to_a.uniq! 

Answer 3

您對map(&:join)電話是什麼在內存中創建數組，因爲map實際上將Enumerator轉換爲數組。根據你想要做什麼，你能避免產生有像這樣的數組：

def each_permutation(string) 
    string.split(//).permutation do |permutaion| 
    yield permutation.join 
    end 
end 

然後用這個方法是這樣的：

each_permutation(my_string) do |s| 
    lookup_string(s) #or whatever you need to do for each string here 
end 

這不重複檢查（沒有呼叫到uniq），但避免創建陣列。對於大型絃樂來說，這仍然可能需要相當長的時間。

但是我懷疑你的情況是有更好的方法來解決你的問題。

實際上，我不需要在任何地方保存結果，我只需要在表中查找它們是否存在。

它看起來像你正在尋找一個字符串在現有的單詞列表中可能的anagrams。如果您採用任何兩個字母並對其中的字符進行排序，則所得的兩個字符串將相同。你可能會改變你的數據結構，以便你有一個散列，鍵是排序的字符串，值是一串字串的字串。然後，而不是根據列表檢查新字符串的所有排列，只需要對字符串中的字符進行排序，然後將其用作查找排列該字符串的所有字符串的列表的關鍵字。

Answer 4

也許你不需要生成該集合的所有元素，而只需要一個隨機或受約束的子集。我寫了一個算法來生成O（n）時間的置換。

首先將密鑰轉換爲the factorial number system的列表表示。然後通過新列表和的舊版迭代地在每個指定的索引處拉出項目。

module Factorial 
    def factorial num; (2..num).inject(:*) || 1; end 

    def factorial_floor num 
    tmp_1 = 0 
    1.upto(1.0/0.0) do |counter| 
     break [tmp_1, counter - 1] if (tmp_2 = factorial counter) > num 
     tmp_1 = tmp_2  ##### 
    end    # # 
    end     # # 
end      # returns [factorial, integer that generates it] 
          # for the factorial closest to without going over num 

class Array; include Factorial 
    def generate_swap_list key 
    swap_list = []    
    key -= (swap_list << (factorial_floor key)).last[0] while key > 0 
    swap_list 
    end 

    def reduce_swap_list swap_list 
    swap_list = swap_list.map { |x|  x[1]     } 
    ((length - 1).downto 0).map { |element| swap_list.count element } 
    end 

    def keyed_permute key 
    apply_swaps reduce_swap_list generate_swap_list key 
    end 

    def apply_swaps swap_list 
    swap_list.map { |index| delete_at index } 
    end 
end 

現在，如果你想隨機抽取一些置換，紅寶石自帶Array.shuffle!，但是這會讓你複製並保存排列或通過permutohedral space進行迭代。或者也許有一種方法可以爲你的目的約束排列空間。

constrained_generator_thing do |val| 
    Array.new(sample_size) {array_to_permute.keyed_permute val} 
end