問題タブ [permutation]

順列のランダムなリストを作成する必要があります。要素は何でもかまいませんが、0 から x-1 までの整数であると仮定します。それぞれが z 要素を含む y リストを作成したいと思います。ルールは、どのリストにも同じ要素が 2 回含まれてはならず、すべてのリストで、各要素が使用される回数は同じ (または可能な限り近い) というものです。たとえば、要素が 0、1、2、3、y が 6、z が 2 の場合、考えられる解決策の 1 つは次のとおりです。

各行には一意の要素のみがあり、3 回以上使用された要素はありません。y が 7 の場合、2 つの要素が 4 回使用され、残りは 3 回使用されます。

リスト内の要素のタイプに関係なく、Python でリストのすべての順列をどのように生成しますか?

例えば：

この質問は、必要なすべてのデータを提供します。指定された間隔[0,N-1]内でK個の非反復整数のシーケンスを生成する効率的なアルゴリズムは何ですか。Kが大きく、 Nに十分近い場合、簡単なアルゴリズム (乱数を生成し、それらをシーケンスに追加する前にそれらが既に存在するかどうかを調べます) は非常にコストがかかります。

リンクされたリストから一連のランダムな要素を効率的に選択するで提供されているアルゴリズムは、必要以上に複雑に見え、いくつかの実装が必要です。関連するすべてのパラメーターを1回のパスで知っている限り、問題なく機能するように見える別のアルゴリズムを見つけました。

この質問と回答に触発されて、F# で一般的な順列アルゴリズムを作成するにはどうすればよいですか? Google はこれに対して有用な回答を提供していません。

編集：以下に私の最良の答えを提供しますが、トーマスの方が優れていると思います（確かに短いです！）

次のサンプル配列が与えられた場合、amountNeeded が満たされるように利用可能な時間の順列をすべて見つけるにはどうすればよいでしょうか? 言い換えれば、follow 配列は以下を生成する必要があります。

リソース 10 と 13 を使用して 2008 年 5 月 14 日の 08:00 から 08:10 まで利用可能

リソース 10 と 13 を使用して 2008 年 5 月 14 日の 08:10 から 08:20 まで利用可能

要素の配列 ( ) と、 2 つの要素を取り、数値を返すarr関数 ( ) があります。f

配列の順列が必要です。これは、 inf(arr[i], arr[i+1])ごとにできるだけ少なくなります。（そしてループする必要があります。つまり、最小化する必要もあります）iarrf(arr[arr.length - 1], arr[0])

また、f距離のように機能するので、f(a,b) == f(b,a)

非効率すぎる場合は最適なソリューションは必要ありませんが、ほとんどリアルタイムで計算する必要があるため、適切に機能し、高速なソリューションが必要です (どのくらいの長さになるかはわかりませんarrが、そうなる可能性があると思います30前後くらい）

私は常に、アルゴリズム、ソート、暗号、バイナリ ツリー、データ圧縮、メモリ操作などに興味を持っていました。

STL 関数 next_perm() を使用した C++ の順列に関する Mark Nelson の記事を読みました。非常に興味深くて便利です。その後、Delphi で次の順列を取得するためのクラス メソッドを 1 つ作成しました。これが現在最もよく使用しているツールだからです。この関数は辞書順で機能します。スタックオーバーフローに関する別のトピックの回答からアルゴのアイデアを得ましたが、今は大きな問題があります。ベクター内の要素が繰り返される順列を使用していますが、必要のない順列がたくさんあります。たとえば、辞書順で 7 つの要素の次の最初の順列があります。

6667778 (6 = 連続 3 回、7 = 連続 3 回)

私の作品では、次のように最大 2 つの要素が連続して繰り返されるパーマのみが有効であると考えています。

6676778 (6 = 連続 2 回、7 = 連続 2 回)

要するに、受け取ったパラメーターに応じて、最大で N 回連続して繰り返される順列のみを返す関数が必要です。

すでにこれを行っているアルゴリズムがあるかどうかは誰にもわかりませんか?

テキストに誤りがあれば申し訳ありませんが、私はまだ英語をあまり上手に話せません。

どうもありがとう、カルロス

私は数学にあまり興味がなかったので、誰かが次のことで私を助けてくれることを願っています.

私は5つの箱を持っています：

ボックスは、白、灰色、または黒のいずれかです (または、0、1、2 と考えてください)。

ボックス セットが取り得る状態はいくつありますか?

考えられるすべての結果を生成する疑似コード (または任意の言語) は何ですか??

つまり...

などなど…

誰かが私にこれを手伝ってくれることに本当に感謝しています。

順列内の実行を単一の数値にマッピングできるだけでなく、後続の数値を削減できるアルゴリズムが必要です。

したがって、実行は、並べ替えられ、順序どおりに並べ替えられた一連の数値です。リスト 1;2;3;5;6;4 には、1;2;3 と 5;6 の 2 つの実行があります。これらを最小の単一の数値に置き換えたいので、ランを削除した後、4 つの要素の順列がある場合、順列は数値 1 ... 4 を使用します。上記では、2 つのランを減らす必要があります。 . 最初の実行は 1、4 は 2 に変換、[5;6] は 3 に変換され、2 番目の基準を保持します。削減された順列を並べ替えてから、マッピングから内部の要素を展開し、元の順列を並べ替えると、同じ結果が得られます。結果の順列には、ランが含まれていてはなりません。

例（実行を強調表示しました）：

今のところ、リストを渡してリストのリストを作成し、実行をグループ化しています。実際、2 番目の部分は、クリーンなソリューションを作成するのが難しい部分です。私は素朴なアプローチを考えました.誰かが私のものよりもうまくできる巧妙なトリックを持っているかどうかに興味があります.私はO(2n + n log n)のようです.

• run を run の head 要素に置き換え、そのデータをハッシュテーブルに挿入する (回復可能性のため)
• ソートされたインデックスを使用して欠落している数字へのマップを作成するためのソート。[1;6;5;4] は [(1,1);(4,2);(5,3);(6,4)] を出力します
• ステップ 1 のリストをステップ 2 で作成したマップに置き換え、変換のためにハッシュテーブルを更新します。

例をもう一度実行します。

この順列を並べ替えて再構築すると、[1;2;3;4]、3->3;4、4->5;6、1;2;3;4;5;6 となります。また、ソートされます。

私はリストを使用しているので、機能的なアプローチが好まれます。コードは必要ありません。もちろん、すべてのアイデアを歓迎します。

編集：

次のように:

マッピングの正確な条件が何であるかは明確ではありません。N 回の実行による順列の順列 [1,2,...,N] の生成が許可されないのはなぜですか? 実行をその実行の数値にマッピングすることを好むようですが、(これが常に可能であるとは限らないため) ある程度の自由を許可しているようです。–

run をその run 内の番号にマップすることは好みませんが (上記を参照してください!)、順序を保持する必要があります。順列 [1;2;3...N]はランであるため、さらに削減できます。それが無効である理由です。順序は別のアルゴリズムの後続の操作で重要になりますが、個々の要素を最後に展開して、元の順列を救うことができます。

Java で物事を順序付けする必要があるリソース スケジューリングの問題がありますが、隣り合うリソースには制限があります。良い例えは、特定の数字のみが隣り合うことができる「数字」の文字列です。私の解決策は再帰的で、小さな文字列に対しては問題なく動作しますが、実行時間は O(X^N) です。ここで、X は可能な桁数 (ベース) であり、N は文字列の長さです。すぐに手に負えなくなります。

以下の互換性マトリックスを使用して、使用できる文字列の例をいくつか示します
。 長さ 1: 0、1、2、3、4
長さ 2:
02、03、14、20、30、41 長さ 3: 020、030 141、202、203、302、303、414

長さ N のすべての文字列をカウントするための私の解決策は、空の文字列で開始し、最初の桁を並べ替え、長さ N-1 のすべての文字列に対して再帰呼び出しを行うことでした。再帰呼び出しは、追加された最後の数字をチェックし、その数字の隣にある可能性のあるすべての順列を試します。毎回 00、01、04 を並べ替えようとしないように、いくつかの最適化が行われています。

それらをすべて列挙しようとする以外に、順列を数えるより良い方法について何か考えはありますか?