問題タブ [permutation]

数字のセット「0」、「1」、「2」、...、「9」があるとします。セット内の各番号の1つだけを含むすべての番号を検索したいと思います。

問題は次のとおりです。プログラムを開始する前に、セットに含まれる数字の数と数字がわかりません。（たとえば、セットには「1」、「3」、「14」の数字を含めることができます。）

インターネットを検索して、私のような問題を解決するために使用するものと思われる「動的計画法」という用語に出くわしましたが、例がわかりませんでした。

誰かがこの問題を解決する方法についてのヒントを教えてもらえますか（おそらく動的計画法で）？

編集：セットに「14」のような数字が含まれている場合、もちろん、セットの異なる数字は何らかの手段で分離する必要があります。たとえば、セットに「1」、「3」、および「14」の数字が含まれている場合、組み合わせは次のようになります。 1-3-14または3-14-1（='-'-文字で区切られた個々の数字）のようなものにします。

編集2：やや似ていると思われる問題の1つをここで説明します。解決策の1つは、動的計画法を使用します。

上記の関数は、str(str[0..mid-1]安定したプレフィックスとして、および置換可能なstr[mid..end]サフィックスとして) の順列を示しています。したがってpermute(str, 0, str.size() - 1)、1 つの文字列のすべての順列を表示するために使用できます。

ただし、関数は再帰アルゴリズムを使用します。多分そのパフォーマンスは改善されるでしょうか？

文字列を並べ替えるより良い方法はありますか?

n個の個別のアイテムのリストが与えられた場合、一度に値のペアを1つずつ交換して、アイテムの各順列をどのようにステップスルーできますか? （私はそれが可能だと思います、確かにそうあるべきだと感じています。）

私が探しているのは、スワップするアイテムの次のペアのインデックスを生成する反復子です。これにより、n!-1 回反復すると n! ある順序でのリストの順列。もう一度繰り返すと、リストが最初の順序に復元される場合はボーナスになりますが、必須ではありません。すべてのペアが最初の (それぞれ最後の) 要素をペアの 1 つとして含む場合、関数は 1 つの値のみを返す必要があるため、それもボーナスになります。

例:- 3 つの要素の場合、最後の要素を最初と 2 番目の要素と交互に交換して順列をループできます。つまり、 (abc) swap 0-2 => (cba) 1-2 (cab) 0-2 ( bac) 1-2 (bca) 0-2 (acb)。

私は C で実装しますが、おそらくほとんどの言語で解決策を見つけることができます。

配列の可能なすべての順列を循環する非常に基本的なものを作成しようとしています。

本当はアセンブルでやっているのですが、Cで説明します。

基本的に、配列があるとしますuint8_t *data=malloc(10);

array 内のバイトの可能なすべての組み合わせを出力するアルゴリズムを作成したいと考えていますdata。

はい、私はそれが遅くなることを知っています（そして多くの値があります）、そして私は本当に複雑な最適化されたバージョンを求めているわけではありません. -特定の条件に従う特定の値を見つけるために型を強制する..

(注、[0,1,2] は [2,1,0] と同じようにカウントされるべきではないため、順列と言います)

編集: また、これを 512 バイトのみの独立したブートローダーに変換するため、あまり多くの libc 関数を使用しないようにしてください。

私はこれを行う方法を知っていますが、私の人生では、頭の中でアルゴリズムを機能させることはできません!

私が探しているのは、構成文字列をバリエーションと順列に展開するために使用できるライブラリまたはクラスのコードです。次のようなもの（構文は私のもので、異なる場合があります）：

これを自分で構築するのはそれほど難しくありませんが、もしそれが周りにあるのなら、わざわざ車輪の再発明をする必要はありません。

結果を計算するアルゴリズムを作成しようとしています。しかし、組み合わせ論の助けが必要です。

1 から 10 までの 2 つの数を選択する必要があるとします。数え方の基本的な規則から、制限がない場合、可能な結果の数は 10 * 10 = 100 です。 2番目を選択した結果）。

最初の数が 2 番目の数よりも大きくなければならない場合、考えられる結果の数はいくつですか?

このコードで、コンマで区切られた文字列に多数の順列 (順序付け) を生成するのに苦労しています...通常の文字列だけを実行し、順列を文字だけで機能させることはできますが、実行するときは少し難しくなりますコンマで区切られた単語で...

プログラムにコンマを認識させるために、StringTokenizer メソッドを使用し、それを arrayList に入れていますが、それは実際に私が得た限りです...ここでも問題は、各単語を並べ替えるのに問題があることです...例を挙げて、この下に投稿し、その下に私のコードを投稿します...皆さんの助けに感謝します! ...そして順列とは、コンマで区切られた単語の順序を意味します

たとえば、BufferedReader で受信する入力が次のようになっているとします。

PrintWriter の出力は次のようになります。

入力には「one,two,three」の後の空白行を含む合計 3 行があり、出力には「yellow,red」の後の空白行 1 行と「three,two,one」の後の空白行 2 行を含む合計 11 行あることに注意してください。 "。テストは自動化され、この形式が必要になるため、正確に正しい形式を取得することが重要です。また、各問題の出力行の順序は重要ではないことに注意してください。これは、出力の最初の 2 行も次のようになる可能性があることを意味します。

ここに私がこれまでに持っているコードがあります...いくつかのものをコメントアウトしたので、それらの部分について心配する必要はありません

いくつかのオブジェクトを含む配列リストがあり、そのオブジェクトの順列を取得する必要がありますか?どうすればよいですか? MyList が、4 つのオブジェクトを含む配列リストであるとします。

arraylist count は 4 なので、4!=24 が必要です。そのオブジェクトの 24 個の順列が必要です。どうすればC#でそれを行うことができますか.私を助けてください.

ありがとう！

順列と組み合わせをカウントするコードがいくつかあり、多数の場合にうまく機能するようにしようとしています。

大規模な中間結果を回避する順列のより良いアルゴリズムを見つけましたが、組み合わせについてはまだ改善できると思います。

これまでのところ、nCr の対称性を反映するために特別なケースを用意しましたが、不必要に大きな中間結果である factorial(r) の呼び出しを回避するより良いアルゴリズムを見つけたいと思っています。この最適化を行わないと、最後の doctest で factorial(99000) を計算するのに時間がかかりすぎます。

組み合わせを数えるより効率的な方法を提案できる人はいますか?

より多くの例のために、より大きなツリー用に編集されました。

いくつかの制限付きで、考えられるすべての順列を生成する必要があるツリー構造があります。次のようなツリーがあるとします。

または、これが少し漠然としている場合は、Perl 表記で行われた同じ構造を次に示します。

(率直に言って、これを読み取り可能なPerl で理解できるなら、私もそれを採用します。)

ツリーをトラバースして、可能な「パス」をすべて最上位から下に取得しようとしています。ノードのすべての子孫グループは、「パス」内の正確に 1 つのメンバーによって表される必要があります。たとえば、A1 では、(B1、B2) の 1 つと (C1) の 1 つを表す必要があります。したがって、A1 から下る各パスは次のいずれかで始まります。

A1 B1 C1

また

A1 B2 C1

B1、B2、または C1 に子がある場合は、それらも表す必要があります。

上記のツリーに対してこれを手作業で処理すると、次の可能性が得られます。

ここの各ノードは DataRow オブジェクトです。

上記のサンプル ツリーを構築するには (後で追加される E および F レベルを除く):

ツリー全体を歩くのは簡単です:

しかし、それは私が必要とするものではありません。この問題は完全なツリー ウォークですが、特定の順序です。何が得られないのですか？これはどんな散歩ですか？

私は 10 年前に Perl で書いたこれの面倒で遅い実装を持っていますが、もう自分のコードを解読することはできません (恥を知れ!)。

編集:グラフと以下のリストは展開されていますが、コードは展開されていません。

グラフを説明できれば、プログラムできます。それが何と呼ばれているか知っていれば、それを調べることができた。しかし、私はできません。ということで、もう少し詳しく説明します。

バケット名は重要ではありません!

各ノードには「子のバケット」があります。A1 には 2 つのバケットがあり、1 つは「B」を含み、もう 1 つは「C」を含みます。それだけの場合 (そして C の下にバケットがなかった場合)、「A1 B1 C1」と「A1 B2 C1」が存在することになります。これは、存在するすべての子バケットから少なくとも 1 つの代表です。

したがって、各バケットには、その子の外積が必要だと思います (ずっと下まで)。