問題タブ [necklaces]

長さ n の k-ary ネックレスは、長さ k のアルファベットからアイテムが抽出される長さ n の順序付けられたリストであり、ローテーションの下で順序付けを共有するすべてのリストの一種で辞書編集的に最初のリストです。

例: (1 2 3) と (1 3 2) は、アルファベット {1 2 3} の長さ 3 のネックレスです。

詳細: http://en.wikipedia.org/wiki/Necklace_(組み合わせ論)

これらをScheme（またはあなたが選んだLisp）で生成したいと思います。私はいくつかの論文を見つけました...
Savage - ネックレスを生成するための新しいアルゴリズム
澤田 - 一定の償却時間でブレスレットを
生成
する 主な理由は、アルファベットまたは必要な長さ (n) を渡していないように見えるためです。私が探しているスキーム手順は、(necklaces n '(ab c...)) という形式です。

最初に k^n リストを生成し、次に回転を除外することで、これらを簡単に生成できます。しかし、それはひどくメモリ効率が悪いです...

ありがとう！

いくつかの背景: 私は、私が抱えている問題を解決するための多かれ少なかれ力ずくの検索アルゴリズムを書いています。これを行うには、すべての可能性を生成して評価し、最適なものを見つける必要があります。評価には実際には時間がかかるため、検索スペースを完全にカバーするソリューションをできるだけ生成しないようにします。さらに、これを実行できる要素が多ければ多いほど良いです。任意の数 K に対して、通常は K です! 順列、およびそれらすべてを生成することは、~10 を超える数では困難です。

実際の問題: 検索空間には、2 つの要素 (N 回の el1 と M 回の el2、ここで K=M+N) のすべての順列が含まれている必要がありますが、次の制限があります。

1. それらは一意である必要があります (つまり、[aabbb] は 1 回だけ必要です)
2. 順列の逆は必要ありません (つまり、[aab] がある場合、[baa] も必要ありません)。
3. 順列は循環的であると考えているため、[aab] = [aba] = [baa]

これができれば、可能性の数は大幅に減少します。K は理想的には大きいため、最初にすべての順列を生成してから、これらの基準に従ってそれらをフィルター処理することは現実的ではありません。私はすでに最初の制限 (以下を参照) を行っており、Matlab の通常の順列関数 (perms) の 2^K から K!/N!M! に数を減らしました。これは大きな勝利です。2 番目の制限は可能性の数を半分に削減するだけですが (最良の場合)、3 番目の制限も可能性の数を実際に削減できるはずだと思います。

誰かがそれを行う方法を知っていて、できれば可能性の数を計算する方法を知っていれば、それは私を大いに助けてくれるでしょう! 説明を希望しますが、コードも問題ありません (C に似た言語、Java(Script)、Python、Ruby、Lisp/Scheme を読むことができます)。

興味のある方へ: これまでに私が持っている一意の順列のみを取得するアルゴリズムは次のとおりです。

• N-1 と M の順列がすべてある場合は、それらを使用して、e1 を挿入することで N と M の順列を見つけることができます。ただし、重複が発生するため、どこにでも挿入することはできません。なぜこれが機能するのかはわかりませんが、古いものから生成される新しい可能性の数を計算できます (私はこれを「ゲイン」と呼びます)。この数は、最初の古い順列の M+1 から始まり、古い順列ごとに 1 ずつ減少してゼロになり、その時点で M に戻ります (M>=N の場合のみ機能します)。したがって、N=3 と M=3 の順列を計算したい場合、N=2 と M=3 の順列が 10 個ある場合、それらのゲインは [4 3 2 1 3 2 1 2 1 1] になります。

熱心なプログラミングを行っているときに、この問題に遭遇しました。問題は次のように表現できます。

マルチセット A について、P(A) が A のすべての可能な順列のセットを表すとします。P(A) は、等価関係が「循環シフトによって関連付けられる可能性がある」状態で、等価クラスである互いに素なサブセットに自然に分割されます。それぞれから正確に 1 つのメンバーを生成することにより、これらすべての等価クラスを列挙します。

たとえば、マルチセット {0, 1, 1, 2} を考えてみましょう。順列 "0112" と "1201" は一意の順列ですが、後者は前者を循環シフトすることで見つけることができ、逆も同様です。目的のアルゴリズムで両方を生成することはできません。

もちろん、強引なアプローチも可能です。循環重複に関係なく、任意のマルチセット置換アルゴリズムを使用して順列を生成し、以前の結果との比較によって見つかった重複を破棄するだけです。ただし、これは実際には非効率的である傾向があります。必要なアルゴリズムは、簿記がゼロではないにしても、最小限で済む必要があります。

この問題への洞察は深く感謝しています。