問題タブ [permutation]

いくつかの背景: 私は、私が抱えている問題を解決するための多かれ少なかれ力ずくの検索アルゴリズムを書いています。これを行うには、すべての可能性を生成して評価し、最適なものを見つける必要があります。評価には実際には時間がかかるため、検索スペースを完全にカバーするソリューションをできるだけ生成しないようにします。さらに、これを実行できる要素が多ければ多いほど良いです。任意の数 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] になります。

順列と順列グループを使用した操作を実装する C++ テンプレート クラスはありますか? そのようなクラスは、積と逆数の検索、乗算などを実装する必要があります。

未知の長さの配列があり、常に均等に割り切れる量の値があります。次に例を示します。

セットを作成する必要があります：

値の順序はvで除算され、セットであることを示します。セット内の値の順序は重要ではありません（頭からランダムにまとめました）。ご覧のとおり、他のセットまたは同じセット内で一致する重複セットはありません。

私はうまくいくものを考え出すために多くの異なることを試みました。私が得た最も近いものは、すべての可能な有効なマッチアップを含むカスケード配列に初期値を入れることでした。

これらの値は、$schedと呼ばれる1つの配列内の配列です。 配列から30を残しました..おっと

数字はチームです。各チームは、各チームを1回プレイする必要があります。スケジュールは、各チームが毎週1試合のみプレイするように設定されます。チームが週に2回以上プレーすることなくすべてのゲームをプレーできるようにするには、スケジュールを数週間にわたって設定する必要があります。

私はすでに順列関数を使用しました、そしてそれは私が同じマッチアップを持たない上記の配列を思いついた方法です。上記のセットに示されているように、スケジュールを出力する方法を理解する必要があります。（同じセットで2回プレーするチームがない限り、例の順序は重要ではないことに注意してください）

それがうまくいかなかったので、私はこれを本来あるべきものを超えて複雑にしていて、もう問題に頭を悩ませることはできません。最初からやり直すことを意味する場合でも、どんな助けでも大歓迎です！

次のようなパラメータの順列を計算することに興味があります。

したがって、List getPermutations（）;のようなものを書くことができます。可能な限りすべての映画のリストを入手できるように。複数のデータ型をサポートすることに興味があります。

アノテーションとListgetPermutations（）メソッドの構築を引き受けるために、誰かが私を正しい方向に向けることができますか？

私は、数字や単語を取り、それらのすべての可能なバリエーションを一緒に見つけ、一緒に探す値の数を定義できるアルゴリズムを探しています。

たとえば、文字列または配列は次のとおりです。

その場合、値2の結果は次のようになります。

したがって、3つのアイテムのセットからの結果は、2つの結果が一致する6つの可能なバリエーションであり
、3つの結果が一致すると次のようになります。

...おそらくもっと多くのオプションさえ

Stackoverflowでこれを行うこの例へのリンクを見つけましたが、これはjavascriptにあります。誰かが、PHPでこれを行う方法を知っているかどうか疑問に思っています。おそらく、すでに何かが構築されているのでしょうか。

http://www.merriampark.com/comb.htm（リンク切れ）

N^2 の数値と N 個のビンのセットがあります。各ビンには、割り当てられたセットからの N 個の番号があると想定されています。私が直面している問題は、数値の各ペアが同じビンを一度だけ共有できるという制約を満たす、数値をビンにマップする一連の分布を見つけることです。

分布は、各行がビンを表す NxN 行列でうまく表現できます。次に問題は、行列の要素の順列のセットを見つけることです。この順列では、数値の各ペアが同じ行を 1 回だけ共有します。どの行であるかは関係ありませんが、2 つの番号が両方とも同じ番号に割り当てられているだけです。

N=8 の制約を満たす 3 つの順列のセットの例:

上記のセットに属さない順列:

2 番目の順列との複数の衝突が原因で、たとえば、両方とも 0 と 32 が 1 つの行でペアになっているためです。

3 つ列挙するのは簡単です。1 つの任意の順列、その転置、および行が前の行列の対角線で構成される行列で構成されます。

ただし、より多くのセットを作成する方法が見つかりません。それは非常に複雑な問題か、解決策が明らかでない単純な問題のいずれかのようです。いずれにせよ、誰かが N=8 の場合に合理的な時間内に解決する方法を知っていたり、問題の適切な学術名を特定したりしてくれれば、私はそれをググることができてありがたいです.

何に役立つのか疑問に思っている方のために説明すると、64 の宛先にトラフィックを提供する、8 つのバッファーを持つクロスバー スイッチのスケジューリング アルゴリズムを探しています。スケジューリング アルゴリズムのこの部分は、入力トラフィックに依存せず、多数の固定配線された宛先バッファ マッピング間を周期的に切り替えます。目標は、宛先アドレスの各ペアが循環期間中に一度だけ同じバッファーを競合するようにし、その期間の長さを最大化することです。言い換えれば、アドレスの各ペアが同じバッファーをめぐって競合することができるだけ少なくなるようにするためです。

編集：

ここに私が持っているいくつかのコードがあります。 コード

貪欲です。通常、3 番目の順列を見つけた後に終了します。しかし、問題を満たす少なくとも N 個の順列のセットが存在する必要があります。

別の方法では、順列 I を選択する際に順列 (I+1..N) を探して、順列 I が最大数の順列からなる解の一部であるかどうかを確認する必要があります。これには、各ステップでチェックするすべての順列を列挙する必要があり、法外なコストがかかります。

次のシナリオを考えてみましょう。

私は数字の配列を持っています：

この配列が結合された場合、番号は1234になります。

数字を入れ替えて、最も高い数字を実現したいと思います。

1234は1243になり、1324になり、1342になります。

アレイでこの変更を行うには、どのアルゴリズムを使用する必要がありますか？

理想的には、この方法でアルゴリズムを使用したいと思います:(配列がウォークスルーと呼ばれる関数としてこのアルゴリズムを持っているとしましょう）

番号のリストは続きます：

1234
1243
1324
1342
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241

文字列を受け取り、可能なすべての大文字と小文字の組み合わせを出力する Ruby のスニペットを書きたかったのです。基本的に、私は覚えているパスワードを持っていますが、大文字の使い方を覚えていません。

これまでのところ、次のものがあります。

これは十分に機能しますが、数字を含む文字列で不必要に機能する必要がないように、ルビイストがそれを改良するのを手伝ってくれるかどうか疑問に思っていました.

たとえば、文字列「tst1」は次を生成します。

私が探している出力は次のとおりです。

何か案は？

ウィキペディアから：

辞書式順序生成

0 ≤ k < n! のすべての数値 k に対して、次のアルゴリズムは、初期シーケンス sj、j = 1、...、n の対応する辞書編集順列を生成します。

この背後にあるロジックは何ですか? それはどのように機能しますか??