問題タブ [permutation]

私は、素敵な備品リストを作成するのに役立つ同僚向けのツールをまとめています。ツールを使って約 3 分の 2 を取得し、さまざまなデータを収集しましたが、レンガの壁にぶつかりました。これは JavaScript の問題ではなく、数学/処理のブレインブロックです。

4 つのチームがあり、ホームとアウェイで互いにプレーする必要があるとします。このツール ( http://www.fixturelist.com/ ) を使用すると、4 チームによるホーム アンド アウェイの試合では、6 週間/ラウンド/何でもかかることがわかります。しかし、私の人生では、それがプログラムでどのように行われたかを理解することはできません.

誰かがこれを処理するロジックを説明できますか?

情報については、この既存のツールを使用しますが、作業する必要がある他の要素/機能があるため、カスタム ジョブを実行します。そのロジックを表現する方法を理解できればいいのに！

OrderElements次の関数を実装するにはどうすればよいですか？

線形の余分なスペースを使用できる場合は簡単ですが、一定の余分なスペースのみで実行できますか？つまり、chars要素をインプレースで直接並べ替えることができますか？

PS：これは試験問題ではありませんでした。私は実際にこの関数が必要です。

明確化：要素の望ましい最終的な順序について誤解があるようです。chars例の結果の配列には、元の配列を参照して、次の要素が含まれている必要があります。

これは

2つの順列（リストで表される）が同じパリティであるかどうかを確認する方法を探しています。それらが偶数または奇数のパリティであるかどうかは興味がなく、等しいだけであることに注意してください。

私はPythonを初めて使用しますが、私の素朴な解決策を以下に返信します。私はPythonの達人が、より少なく、よりエレガントなPythonコードで同じことを達成するためのいくつかのクールなトリックを見せてくれるのを楽しみにしています。

n 個の要素があります。例として、7 つの要素、1234567 としましょう。7 つあることはわかっています。= これらの 7 つの要素の可能な 5040 順列。

2 つの関数で構成される高速なアルゴリズムが必要です。

f(数値) は、0 から 5039 までの数値を一意の順列にマップし、

f'(permutation) は、順列を生成元の数値にマップします。

各順列に独自の番号がある場合、番号と順列の対応は気にしません。

したがって、たとえば、次のような関数があるかもしれません

頭に浮かぶ最速のアルゴリズムは、すべての順列を列挙し、両方向のルックアップ テーブルを作成することです。テーブルが作成されると、f(0) は O(1) になり、f('1234567') は文字列のルックアップ。ただし、これは特に n が大きくなるとメモリを消費します。

メモリの欠点がなく、すばやく動作する別のアルゴリズムを提案できる人はいますか?

Set.Make(t) によって返される 2 つのセットがあります。2 つの値の可能なすべての組み合わせを生成したいと思います。これどうやってするの？

これはいくつかのペアを生成するために機能しますが、すべてではありません:

これはJavaでそれを行います：

だから私は正規表現パターンを持っており、そのパターンから許可されるすべてのテキスト順列を生成したいと考えています。

例：

これにより、以下の文字列のリストが返されます。

私の名前はスティーブです

私の本当の名前はスティーブです

私の生物学的名前はスティーブです

更新: 明らかに、正規表現には無限の数の一致があるため、(?:biological|real)? のようにオプションの文字列リテラルからのみ生成したいだけです。上記の私の例から。(.)* のようなものは一致が多すぎるため、そこから生成することはありません。

特定の範囲（通常は0から約1000）の番号があります。アルゴリズムは、この範囲からいくつかの数値を選択します（約3から10の数値）。この選択は非常に頻繁に行われるため、選択した数値の順列がすでに選択されているかどうかを確認する必要があります。

たとえば、1つのステップが選択[1, 10, 3, 18]され、別のステップが選択されると[10, 18, 3, 1]、2番目の選択は順列であるため破棄できます。

このチェックを非常に速く行う必要があります。今、私はすべての配列をハッシュマップに入れ、カスタムハッシュ関数を使用しています。つまり、すべての要素を合計するだけなので、1 + 10 + 3 + 18 = 32、さらに10 + 18 + 3 + 1=32です。等しい場合は、ビットセットを使用して、要素が両方のセットにあるかどうかをすばやく確認します（ビットセットを使用する場合は並べ替えは必要ありませんが、数値の範囲がわかっていて大きすぎない場合にのみ機能します）。

これは問題なく機能しますが、多くの衝突を生成する可能性があるため、equals（）メソッドが頻繁に呼び出されます。順列をチェックするより速い方法があるかどうか疑問に思いましたか？

順列に適したハッシュ関数はありますか？

アップデート

私は少しベンチマークを行いました：0から6の範囲の数値のすべての組み合わせ、および配列の長さ1から9を生成します。3003の可能な順列があり、この多くの異なるハッシュの近くで適切なハッシュを生成する必要があります（32ビットの数値を使用します）ハッシュの場合）：

• 追加するだけの41の異なるハッシュ（したがって、衝突がたくさんあります）
• 値を一緒にXORするための8つの異なるハッシュ
• 乗算用の286の異なるハッシュ
• （R + 2e）の3003の異なるハッシュと、abcが示唆しているように乗算（Rに1779033703を使用）

したがって、abcのハッシュは非常に高速に計算でき、他のすべてのハッシュよりもはるかに優れています。ありがとう！

PS：遅くなりすぎるので、必要のないときに値を並べ替えたくありません。

S1 = {s11,s12,s13)、S2 = {s21,s22,s23) などのセットを SN まで持っています。各セットから 1 つの要素のみ。

例：

私の順列は次のとおりです。

どうすればそれを行うことができますか？(それぞれからランダムに 1 つを選択してマージすることもできますが、それは私の知る限りでも悪い考えです)。

一般化のために、各セットに「n」個の要素があると仮定します。Cでの実装を検討しています。「N」と「n」は固定されていないことに注意してください。

この人たちと一緒に私を助けてくれることを願っています。それは仕事を助けるものではありません。非常に勤勉なボランティアの慈善団体のためのものであり、彼らは現在持っているものよりも混乱や煩わしさの少ないタイムテーブルシステムを実際に使用することができます.

これを（確かに）自動化する優れたサードパーティ製アプリを誰かが知っていれば、それはほぼ同じです. ただ...教室を予約するためのようなランダムな時間割を提案しないでください.彼らはこれを行うことができないと思います.

読んでいただきありがとうございます。私はそれが大きな投稿であることを知っています。ただし、これを明確に文書化し、自分で努力したことを示すために最善を尽くしています.

問題

次の基準を満たすワーカーのシフトを生成するワーカー/タイムスロット スケジューリング アルゴリズムが必要です。

入力データ

処理

上記から、シフトと労働者は、処理する 2 つの主要な入力変数です。

各シフトには、必要な労働者の最小数と最大数があります。シフトの最小要件を満たすことは成功に不可欠ですが、他のすべてが失敗した場合、手動で埋めるギャップのある勤務表は「エラー」よりも優れています:) 主なアルゴリズムの問​​題は、十分な場合に不必要なギャップがあってはならないということです労働者が利用可能です。

理想的には、シフトの最大数の労働者が満たされることですが、これは他の制約に比べて優先度が最も低いため、何かを与える必要がある場合は、これにする必要があります。

柔軟な制約

これらは少し柔軟性があり、「完璧な」ソリューションが見つからない場合は、境界を少し広げることができます。ただし、この柔軟性は、ランダムに悪用されるのではなく、最後の手段であるべきです。理想的には、柔軟性は「fudge_factor」変数などで構成可能です。

• 2 つのシフトの間に最小時間間隔があります。したがって、たとえば、同じ日に 2 つのシフトをスケジュールするべきではありません。
• 労働者が特定の期間 (たとえば、1 か月) に行うことができるシフトの最大数があります。
• 1 か月に行うことができる特定のシフトの最大数があります (夜勤など)。

あると便利ですが、必須ではありません

上記を実行し、これらの一部またはすべてを含むアルゴリズムを考え出すことができれば、私は非常に感銘を受け、感謝します. これらのビットを個別に実行するアドオン スクリプトも素晴らしいでしょう。

• 重複するシフト。たとえば、「フロントデスク」のシフトと「バックオフィス」のシフトが同時に発生するように指定できるとよいでしょう。これは、異なるシフト データを使用してプログラムを個別に呼び出すことで実行できますが、特定の期間内に複数のシフトに人をスケジュールすることに関する制約が失われる場合があります。

• (グローバルではなく) 作業者ごとに指定可能な、作業者の最小再スケジュール期間。たとえば、Joe が過労を感じているか、個人的な問題に対処している場合、または初心者であり、他の作業者よりも少ない頻度でスケジュールすることをお勧めします。

• 利用可能な労働者が適合しない場合に、最小シフト数を満たすためにスタッフを選択する自動/ランダム/公正な方法。

• 突然のキャンセルに対処し、他のシフトを再調整せずにギャップを埋める方法。

出力テスト

おそらく、アルゴリズムはできるだけ多くの一致するソリューションを生成する必要があります。各ソリューションは次のようになります。

上記のデータが与えられた場合の個々のソリューションのテスト関数を次に示します。これは正しいと思いますが、それについてのピアレビューもいただければ幸いです。

試み

これを遺伝的アルゴリズムで実装しようとしましたが、完全に調整できないようです。そのため、基本原理は単一シフトで機能するように見えますが、いくつかのシフトといくつかの簡単なケースでさえ解決できません。労働者。

私の最新の試みは、可能なすべての順列を解決策として生成し、次に制約を満たさない順列を絞り込むことです。これははるかに迅速に機能するようで、さらに理解を深めましたが、順列の生成を支援するために python 2.6 の itertools.product() を使用していますが、うまくいきません。正直なところ、問題は私の頭にうまく収まらないので、多くのバグがあっても驚かないでしょう:)

現在、このコードは、models.py と rota.py の 2 つのファイルにあります。models.py は次のようになります。

と rota.py は次のようになります。

結果の前にデバッグ出力を切り取ると、現在次のようになります。

プロジェクト オイラーの問題の 1 つを解決しようとしています。結果として、セットのすべての可能なパーティションを任意の順序で見つけるのに役立つアルゴリズムが必要です。

たとえば、 set が与えられた場合2 3 3 5:

等々。セットのメンバーのほぼすべての可能な組み合わせ。もちろん、ネットを検索しましたが、私は高度な数学ではなくプログラマーを話すので、直接役立つ情報はあまり見つかりませんでした。

誰でもこれで私を助けることができますか? 私は BASIC から Haskell まで、ほとんどすべてのプログラミング言語を読むことができるので、好きな言語で投稿してください。