1

したがって、文字列のすべての可能な順列を取得する必要があります。

私が今持っているのはこれです：

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

さて、私の問題は何ですか：このメソッドは小さな文字列には問題なく機能しますが、サイズが15、場合によっては20のような文字列でも使用できるようにしたいと考えています。また、このメソッドでは大量のメモリ（> 1gb）を使用します。 ）そして私の質問は、それほど多くのメモリを使用しないように何を変更できるかということです。

順列を生成するためのより良い方法はありますか？それらをファイルシステムに永続化し、必要なときに取得する必要がありますか（これによりメソッドが遅くなる可能性があるためではないことを願っています）？

私に何ができる？

アップデート：

実際には、結果をどこにでも保存する必要はありません。テーブル内でそれぞれを検索して、結果が存在するかどうかを確認する必要があります。

4

4 に答える 4

4

佐和が言ったことを繰り返すだけです。あなたは範囲を理解していますか？n要素の順列の数はですn!。それはあなたが得ることができる最も積極的な等差数列演算についてです。n1〜20の結果は次のとおりです。

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

最後の数は約2兆、つまり20億です。

これは2265820000ギガバイトです。

結果を一日中ディスクに保存することができます-世界中のすべてのGoogleデータセンターを所有していない限り、ここではほとんど運が悪いでしょう:)

于 2013-02-02T23:34:41.583 に答える
4

への呼び出しは、実際には列挙子を配列に変えるため、map(&:join)メモリ内に配列を作成しているものです。mapやりたいことに応じて、次のような配列の作成を回避できます。

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）が、配列の作成を回避します。大きな文字列の場合、これにはまだかなり長い時間がかかる可能性があります。

しかし、あなたの場合、あなたの問題を解決するためのより良い方法があると思います。

実際には、結果をどこにでも保存する必要はありません。テーブル内でそれぞれを検索して、結果が存在するかどうかを確認する必要があります。

既存の単語リストで文字列の可能なアナグラムを探しているようです。2つのアナグラムを取得してその中の文字を並べ替えると、結果の2つの文字列は同じになります。おそらく、データ構造を変更してハッシュを作成します。キーは並べ替えられた文字列であり、値はその文字列のアナグラムである単語のリストです。次に、新しい文字列のすべての順列をリストと照合する代わりに、文字列内の文字を並べ替え、それをキーとして使用して、その文字列の順列であるすべての文字列のリストを検索する必要があります。

于 2013-02-03T05:21:00.850 に答える
4

おそらく、セットのすべての要素を生成する必要はなく、ランダムまたは制約されたサブセットのみを生成する必要があります。O（n）時間でm番目の順列を生成するアルゴリズムを作成しました。

まず、階乗法でキーをそれ自体のリスト表現に変換します。次に、新しいリストと古いリストで指定された各インデックスでアイテムを繰り返し引き出します。

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

ここで、いくつかの順列をランダムにサンプリングする場合、rubyにはが付属してArray.shuffle!いますが、これにより、順列をコピーして保存したり、順列空間を反復処理したりできます。あるいは、目的に合わせて順列スペースを制限する方法があるかもしれません。

constrained_generator_thing do |val|
    Array.new(sample_size) {array_to_permute.keyed_permute val}
end
于 2013-12-08T19:00:45.397 に答える
0

おそらく私は明白なことを見逃していますが、なぜしませんか

['a','a','b'].permutation.to_a.uniq!
于 2013-02-02T23:19:39.677 に答える