問題タブ [combinations]

荷物があるとします。A 地点から B 地点、B 地点から C 地点、そして最後に C 地点から D 地点に移動する必要があります。5 日以内に到達する必要があり、できるだけ少ない金額で済みます。各レグには 3 つの可能な荷送人があり、各レグにはそれぞれ異なる時間とコストがあります。

プログラムで最適な組み合わせを見つけるにはどうすればよいでしょうか?

これまでの私の最善の試み（3番目または4番目のアルゴリズム）は次のとおりです。

1. 各区間で最長の荷送人を見つける
2. 最も「高価な」ものを排除する
3. 各区間で最も安い荷送人を見つける
4. 総費用と日数を計算する
5. 日数が許容できる場合は終了、そうでない場合は 1 に移動

PHP ですばやくモックアップします (以下のテスト配列は問題なく動作しますが、上記のテスト配列で試してみると、正しい組み合わせが見つからないことに注意してください)。

文字通り、各組み合わせを 1 つずつ (一連のループを使用して) 作成し、それぞれの合計「スコア」を合計して、最高のものを見つけるという、ある種のことを実際に行う必要があると思います....

編集：明確にするために、これは「宿題」の課題ではありません（私は学校にいません）。それは私の現在のプロジェクトの一部です。

要件は (いつものように) 常に変化しています。この問題に取り組み始めた時点で現在の制約が与えられていたとしたら、A* アルゴリズムの変形 (またはダイクストラまたは最短経路またはシンプレックスなど) を使用していたでしょう。しかし、すべてが変形し、変化しており、それが私を今いる場所に導きます.

つまり、これまでに行ったすべてのがらくたを忘れて、パス検索アルゴリズムである、使用すべきだとわかっているものを使用する必要があることを意味していると思います。

次のことを行うコードを作成しようとしています。

0 から 9 までの数字を取り、この数字に 1 つ以上の文字を割り当てます。例えば：

0123 のようなコードがある場合、それをエンコードするのは簡単です。それは明らかにコード NLTD を構成します。5、6、8 などの数字が導入されると、状況が異なります。051 のような数値は、複数の可能性をもたらします。

NVLとNFL

これは、5、6、8 などの数桁を含む長い数字ではさらに「悪化」することは明らかです。

私は数学がかなり苦手なので、プログラムに大量の数字を入力して、可能なすべての文字の組み合わせを吐き出すことができる適切な解決策をまだ考え出すことができませんでした。わからないので、少しでも参考になれば幸いです。順列と組み合わせに関する情報を掘り起こしましたが、うまくいきませんでした。

提案/手がかりをありがとう。コードを書くために必要な言語は PHP ですが、一般的なヒントをいただければ幸いです。

アップデート：

もう少し背景: (素早い回答に感謝します!)

私の質問の背後にあるアイデアは、人々が覚えたい数字をはるかに覚えやすい単語に簡単に変換できるようにするスクリプトを作成することです。これは、「疑似数秘術」と呼ばれることもあります。

可能なすべての組み合わせをスクリプトから取得し、それを削除された単語のデータベースに対して保持するようにしたいと考えています。これらの削除された単語は、辞書から取得したもので、質問で言及したすべての文字が削除されています。そうすれば、通常、エンコードする数値を 1 つ以上のデータベース レコードに簡単に関連付けることができます。そして、それが起こると、覚えたかった数字を覚えるために使用できる単語のリストができあがります。

文字の配列を引数として取り、それらの文字の数を選択する関数を作成したいと思います。

8文字の配列を提供し、その中から3文字を選択するとします。次に、次のようになります。

それぞれ3文字で構成される配列（または単語）。

私は4つのバイナリビットを持っています

通常、答えは簡単です。2^4、つまり 16 の異なる組み合わせです。次のようになります。

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

ただし、LSB (ビット 0) は反復ごとに状態が変化します。

すべての反復でビットの状態が 1 回だけ変化するアルゴリズムが必要です。つまり、すべてのビットが MSB (ビット 3) のように動作する必要があります。

これどうやってするの？

編集

ほとんどの人は、可能な解決策が 5 つしかないことに収束しているようです。ただし、これは値の開始点と終了点があることを前提としています。これは問題ではないので、よりよく説明するために実際のシナリオを示します。

4 つの出力を提供するデジタル目覚まし時計があるとします。各出力は、特定の時間にオンになり、特定の時間にオフになるようにプログラムでき、互いに独立してプログラムできます。出力 1 は午前 1 時にオンになり、午前 3 時にオフになるようにプログラムでき、出力 2 は午後 7 時にオンになり、午前 2 時にオフになるようにプログラムできます。各出力をオンにしておくことができる時間に制限はありません。

今度は、この目覚まし時計をコンピューターに接続して、現在の正確な時刻にできるだけ近づけたいと考えています。たとえば、時計が午後 2 時 15 分である場合、コンピュータはアラームが午後 12 時から午後 6 時の範囲内にあることを認識します。可能な限り最小の範囲を取得できるようにしたい。私が得ることができる最小の可能な範囲は何ですか?

15個の数字のリストがあり、それらの数字の32,768の組み合わせすべてを生成するコードを作成する必要があります。

私が探しているものを明らかに実行するコードを（グーグルで）見つけましたが、コードはかなり不透明であり、使用することに慎重です。さらに、もっとエレガントな解決策が必要だと感じています。

私が思い浮かぶのは、1〜32768の10進数をループしてバイナリに変換し、バイナリ表現をフィルターとして使用して適切な数値を選択することだけです。

誰かがより良い方法を知っていますか？使用してmap()、多分？

問題

32ビットの数値を作成する必要があり（符号付きか符号なしかは関係ありません。とにかく最上位ビットが設定されることはありません）、各数値には特定の数のビットが設定されている必要があります。

素朴な解決策

もちろん、最も簡単な解決策はゼロから始めることです。ループ内では、数値が 1 ずつ増加し、ビット数がカウントされます。カウントが目的の値である場合、数値がリストに格納されます。そうでない場合は、ループが繰り返されます。十分な数が見つかった場合、ループは停止します。もちろん、これは問題なく動作しますが、必要なビット数が非常に多くなると、非常に遅くなります。

より良いソリューション

(たとえば) 5 ビットが設定されている最も単純な数値は、最初の 5 ビットが設定されている数値です。この番号は簡単に作成できます。ループ内で最初のビットが設定され、数値が 1 つ左にシフトされます。このループは 5 回実行され、5 ビットが設定された最初の数値が見つかりました。次の数も簡単に作成できます。ここで、数値が 6 ビット幅であると仮定し、最高の数値は設定されていません。ここで、最初の 0 ビットを右にシフトし始め、101111、110111、111011、111101、111110 を取得します。前に別の 0 を追加してこのプロセスを繰り返すことで、これを繰り返すことができます。0111110、1011110、1101110 など。ただし、この単純なアプローチを使用すると、1010111 などの数字が除外されるため、数字が必要以上に速く成長します。

次の数値のビット数に関係なく、設定する必要があるビット数に関係なく、使用できるすべての可能な順列、一般的なアプローチを作成するより良い方法はありますか?

2 つのオブジェクトを表示するページがあり、ユーザーはそのうちの 1 つを選択します。好みと組み合わせを MSSQL データベースに記録し、最終的に次のようなデータを保存します。

ここで、オブジェクトの組み合わせ (1,2 / 2,1) を二度と表示したくありません。

では、ランダムな組み合わせを生成して、以前に表示した組み合わせを除外してユーザーに表示するにはどうすればよいでしょうか?

これは本当に簡単な質問のように思えますが、ほとんどのプログラマーと同じように、私は睡眠とコーヒーが不足しているので、あなたの助けに感謝します:-)

非常に単純なアプローチは次のようなものです (この関数へのすべての呼び出しは、ユーザーが既に nCr (n はアイテム数、r は 2) と同じ回数評価しているかどうかを確認するためにチェックでラップする必要があります):

編集

一部の SQL を使用して、完全ではないすべてのアイテムのリストを生成できます (つまり、ユーザーが見たことのないアイテムを含む組み合わせがあります) が、特に役立つとは思いません。

2 つのランダムな項目を選択する前に、すべての可能な組み合わせを生成し、既に表示されているものを削除することも想像できますが、これは別のひどい解決策です。

1 つの可能性 (大きな n に対してメモリを大量に消費する) は、考えられるすべての組み合わせを生成し、combinationId を評価に格納することです。次に、組み合わせの対称関係を反映するためにいくつかの変更を加えて、すべての組み合わせの SELECT を行うことができます。

アイテムのリストがあり、各アイテムには数量があります。

または、これは次のように表示できます。

[1,2,3] == [3,2,1]これらのアイテムのすべての組み合わせのリストを取得するにはどうすればよいでしょうか。順序はまったく重要ではなく (したがって)、すべてのアイテムが結果に存在する必要はないことを念頭に置いてください。

出力は次のようになると思います。

または、さらに良い：