大きな組の置換を効果的に保存する方法は？

Question

は、我々が要素のリストを持っているとしましょう：

[{dog,1},{dog,2},{cat,1},{cat,2},{bird,1},{bird,2},...] 

私はRAMで、このリストのすべての可能なpermutationsを保存したいと思います。

リストはかなり長く（10要素以上）なる可能性があるので、それを格納するには多くのスペースが必要です（階乗N）。

たとえば、約70バイトの領域を消費し、12個の要素を持つリストがある場合は、12! * 70 ~ 31 GBが必要です。リストに要素を1つだけ追加すると、並べ替えをRAMに格納することができなくなる可能性があります。

次のErlang表現よりもメモリ内のすべての順列を保持する効率的な表現がありますか？

[{dog,1},{dog,2},{cat,1},{cat,2},{bird,1},{bird,2},...] 

は、（Iは原子dogが原子テーブルに一度だけ格納されていることを知っているが、それはすべての順列で繰り返されるので、N個のメモリを要します）。

多分、これらの並べ替えは何らかの種類のバイト表現で保存できますか？ （申し訳ありませんが、私はバイトとバイナリの初心者です）。

結局のところ、それはちょうど同じ要素ですが、異なる方法で再配置されます。

Answer 1

なぜそれらを遅延して生成しませんか？各リストからインデックスを作成し、新しい要素を尋ねられたらすぐに組み合わせを作成します。そうすれば、ソース要素の初期リストとメモリのインデックスをいつでも保存するだけで済みます。例えば

（あなたが順列を反復処理する必要がある場合）：あなたがindex_bの最大値に達し

-record(perm, {list_a, list_b, index_a, index_b}). 

毎回、あなたは0にそれをリセットし、1でindex_aをインクリメント。リストのN番目の要素（Nはインデックス）にアクセスすると、任意の置換インスタンスを再作成できます。

もちろん、これは、並べ替えが生成されるたびにリストをトラバースする必要があることを意味します。自分自身を指標として、これを回避するには、リストを使用することができます。

-record(perm2, {list_a, list_b, list_b_orig}). 

、次の順列を生成list_bから新しい要素をポップし、list_aの頭にそれを追加するには。 list_bが空の場合は、list_aの頭を取り除き、list_bをlist_b_origに保存されている元の値に戻してやり直してください。

Answer 2

多分それを圧縮すれば仕事はできますか？

Zlibモジュールはこのような処理をしているようです。

Answer 3

N個の要素のリストがある場合は、N！順列。したがって、数字1からNまでのマッピングを作成できれば！ （または0〜N！-1）を再現可能な方法でこれらの置換に適用すると、Nを保存する必要はありません。要素のリストですが、N！数字。

しかし、私がNを保存する理由はありません。数字？彼らは変化しないので、私たちはそれらを保存する必要はありません。私たちは最大の要素インデックスで定義されている上限を必要とします。これはNです。これは既にコードに格納されている必要があります。

Erlangを知らないのは残念ですが、I wrote a functional algorithm in Scalaは、再現性のある方法で任意のサイズの順列を生成できます。

たとえば、数字（1~12）の123456790番目の並べ替えはList（4,2,1,5,12,7,10,8,11,9,3,6）です。

特別なボーナスとして、このアルゴリズムはソートされた方法で順列を生成します。再現可能な方法ですべての並べ替えを見つけることができますが、順序はありません。

def permutationIndex (idx: Int, list: List [Int]) : List [Int] = { 
    if (list.isEmpty) list else { 
    val el = list (idx % list.size) 
    el :: permutationIndex (idx/list.size, list.remove (_ == el))}}