3

要素のリストがあるとしましょう:

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

このリストのすべての可能な順列を RAMに保存したいと思います。

リストは非常に長くなる可能性があるため (10 要素以上)、それを格納するには多くのスペースが必要です (階乗 N)。

たとえば、約 70 バイトのスペースを消費し、12 の要素を持つリストがある場合、12! * 70 ~ 31 GB. リストにもう 1 つの要素を追加すると、順列を RAM に格納できなくなる可能性があります。

次のErlang表現よりも、すべての順列をメモリに保持するためのより効率的な表現はありますか?

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

（アトムはアトムテーブルに一度だけ格納されることは知っていdogますが、順列ごとに繰り返されるため、N個のメモリが必要です）。

たぶん、これらの順列は、ある種のバイト表現で保存できますか? (申し訳ありませんが、私はバイトとバイナリの初心者です)。

結局のところ、それはまったく同じ要素ですが、さまざまな方法で再配置されています.

4

3 に答える 3

3

それらを怠惰に生産してみませんか？各リストからインデックスを保持し、新しい要素を求められたら、その場で組み合わせを作成します。そうすれば、ソース要素の初期リストとインデックスをいつでもメモリに保存するだけで済みます。

例（順列を反復する必要がある場合）：

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

の最大値に達するたびに、index_bそれを にリセットして 10ずつ増やしますindex_a。次に、リストの N 番目の要素 (N はインデックス) にアクセスすると、順列インスタンスを再作成できます。

もちろん、これは、順列が生成されるたびにリストをトラバースする必要があることを意味します。これを避けるために、リスト自体をインデックスとして使用できます。

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

次の順列を生成するには、 から新しい要素をポップしlist_bて、 の先頭に追加しますlist_a。list_bが空の場合は、 の先頭を削除し、に保存されているオリジナルにlist_a設定してやり直します。list_blist_b_orig

于 2012-01-04T09:01:58.783 に答える
1

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

しかし、やめてください-なぜNを保存する必要があるのですか？数字？それらは変更されないため、保存する必要はありません。必要なのは上限だけです。上限は、最大の要素インデックスであるNによって定義されます。これは、コードに既に格納されている必要があります。

Erlangを知らなくて申し訳ありませんが、Scalaで、再現可能な方法で任意のサイズの順列を生成できる機能アルゴリズムを作成しました。

たとえば、123456790番目の数字（1から12）の順列は、リスト（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))}}
于 2012-01-23T09:31:54.330 に答える
0

多分それを圧縮することは仕事をするでしょうか？

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

于 2012-01-04T07:50:28.713 に答える