問題タブ [combinatorics]

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

例えば：

私は誰かが簡単だと思ったプログラムを書くのを手伝おうとしていますが、もちろん決してそうではありません:)

クラスの名簿 (通常は 10 ～ 20 人の学生) を作成し、各クラスメートを効果的に一意にペアにして、一意のグループを作成しようとしています。したがって、10 人のクラスでは、9 つ​​のグループを持つことができます。

奇数の学生も処理できる必要があり、混乱を招きます。

Javaでこれを行うことを検討していましたが、それは柔軟です。a）無限ループではない（すでにパートナーになっている2人で終わる）、およびb）クラスサイズが小さいため、スペースよりも効率的な時間を目指しています！

ありがとう！

このメソッドを任意の数の引数に対して機能させたいのですが、コード生成(多くの醜いコード)でそれを行うことができますが、再帰で行うことができますか? もしそうならどのように？私は再帰を理解していますが、これを書く方法がわかりません。

長さ 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 リストを生成し、次に回転を除外することで、これらを簡単に生成できます。しかし、それはひどくメモリ効率が悪いです...

ありがとう！

Clojure でそれらの遅延リストを作成できるような方法でセットの順列を生成するアルゴリズムを探しています。つまり、要求するまで各順列が計算されず、すべての順列を一度にメモリに格納する必要がない順列のリストを繰り返し処理したいと考えています。

または、特定のセットが与えられた場合、そのセットの「次の」順列を返すアルゴリズムを探しています。これにより、独自の出力で関数を繰り返し呼び出すと、元のセットのすべての順列が循環します。いくつかの順序 (順序は重要ではありません)。

そのようなアルゴリズムはありますか？私が見た順列生成アルゴリズムのほとんどは、それらをすべて一度に (通常は再帰的に) 生成する傾向があり、非常に大きなセットには拡張できません。Clojure (または別の関数型言語) での実装は役に立ちますが、疑似コードから理解できます。

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

したがって、実行は、並べ替えられ、順序どおりに並べ替えられた一連の数値です。リスト 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]はランであるため、さらに削減できます。それが無効である理由です。順序は別のアルゴリズムの後続の操作で重要になりますが、個々の要素を最後に展開して、元の順列を救うことができます。

例 (または実際のユースケース) が NP-Complete と見なされるかどうかはわかりませんが、これが利用可能なアルゴリズムであると仮定して、以下を実行する最も Pythonic な方法について疑問に思っています。

あなたが持っているとしましょう：

人のグループを必要とするいくつかの操作。（重要な値は、人が幸せか悲しいかです。）

したがって、PersonA、PersonB、PersonC、PersonD が与えられた場合、悲しい人物と幸せな人物の可能な 2**4 の組み合わせのリストを完成させたいと思います。すなわち

これを行う良いPythonicの方法はありますか? 私はリスト内包表記について考えていました (そして、オブジェクトを呼び出して true と false の 2 つのオブジェクトが返されるようにオブジェクトを変更します) が、私が見た内包表記では、事前に人の数を知る必要があります。人数に関係なくやってみたいです。

編集 : これに対して実行する操作が、より大きな問題セットの一部であると仮定します。問題を解決するには、特定のセットの Person のすべての値をテストする必要があります。(つまり、これは現在NP完全に見えないことを知っています=))何かアイデアはありますか?

ありがとう！

特に理由はありませんが、1...n の間の k 個の整数のすべての可能な選択肢を生成するアルゴリズムを探すことにしました。ここで、k 個の整数の順序は重要ではありません (n は k のものを選択します)。

まったく同じ理由で、まったく理由はありませんが、C# でも実装しました。私の質問は：

私のアルゴリズムやコードに誤りはありますか? さらに重要なのは、より良いアルゴリズムを提案できますか?

コード自体よりもアルゴリズムに注意を払ってください。これは私がこれまでに書いた中で最も美しいコードではありませんが、エラーが発生した場合は教えてください。

編集：アルゴリズムの説明-

• k 個のインデックスを保持します。
• これにより、 forループのネストされた k が作成されます。ここで、ループ i のインデックスは index[i] です。
• これは、インデックス[i+1] がインデックス[i] のループ内にネストされたループに属するループのkをシミュレートします。
• インデックス[i] は、インデックス[i - 1] + 1 から n - k + i + 1 まで実行されます。

コード：

長い質問で申し訳ありません。ブログ投稿に適しているかもしれませんが、ここでコミュニティの意見を求めています。

ありがとう、
アサフ

サイズnの集合Sが与えられ、これはサイズn1、..、nkのクラス（s1、..、sk）に分割されます。当然、n = n1 + ...+nkであることが成り立ちます。

このパーティショニングの要素を組み合わせて、各組み合わせに各クラスの要素が1つだけ含まれるようにする方法の数を知りたいと思います。

s1からn1要素、s2からn2要素などを選択できるので、n1 + .. + nkを保持する任意のn1、.. nkのmax（n1 * .. * nk）の解を探しています。 =n。

これは線形最適化の問題だと感じていますが、学部生として学んだので長すぎます。誰かがこれを計算する方法を覚えていることを願っています。