問題タブ [combinatorics]

シード文字列が与えられた場合、最大で 2 つの位置が異なる隣接文字列を見つけたいと考えています。文字列の生成に関係するすべての数字は 4 つだけです (つまり、0、1、2、3)。これは私が言いたいことの例です：

しかし、私のこのコードが正しく生成されないのはなぜでしょうか? 特にシード文字列が「000」以外の場合。

特に速度の向上を伴う他のアプローチも歓迎されます。長さ 34 ～ 36 の数百万のシード タグを処理するためです。

重複要素を含むセット** S が与えられた場合、各サブセットが一意である S のすべての可能なサブセットの総数をどのように決定できますか。

たとえば、S = {A, B, B} とし、K をすべての部分集合の集合とすると、K = {{}, {A}, {B}, {A, B}, {B, B}, {A, B, B}} したがって |K| = 6。

別の例として、S = {A, A, B, B} の場合、K = {{}, {A}, {B}, {A, B}, {A, A}, {B, B}, {A、B、B}、{A、A、B}、{A、A、B、B}}、したがって |K| = 9

S が一意の要素のみを持つ実集合である場合、|K| は簡単にわかります。= 2^|S|。

この値 |K| を計算する式は何ですか? すべてのサブセットを生成せずに、「セット」S (重複あり) を指定しますか?

** 技術的にはセットではありません。

これは、Pythonでリストのすべての順列を生成する方法に関する質問に関連しています

次の基準に一致するすべての順列を生成する方法：2つの順列が互いに逆の場合（つまり、[1,2,3,4]と[4,3,2,1]）、それらは等しいと見なされ、そのうちの1つだけが最終結果になるはずです。

例：

一意の整数を含むリストを並べ替えています。

結果として生じる順列の数が多くなるので、可能であればPythonのジェネレーターを使用したいと思います。

編集：可能であれば、すべての順列のリストをメモリに保存したくありません。

アイテムのペアの複数のリストがあるシナリオを考えると、たとえば次のようになります。

1. {12,13,14,23,24}
2. {14,15,25}
3. {16,17,25,26,36}

ここで、12 はアイテム '1' と '2' のペアです (したがって、21 は 12 に相当します)。単一のアイテムが存在しないように、各リストからアイテムのペアを選択できる方法の数を数えたいと考えています。繰り返した。各リストからペアを 1 つだけ選択する必要があります。各リスト内のアイテムの数とリストの数は任意ですが、リストごとに少なくとも 1 つのアイテムのペアを持つリストが少なくとも 2 つあると想定できます。そして、ペアは有限のアルファベットの記号から作られ、数字[1-9]を想定しています。また、リストに重複ペア {12,12} または {12,21} を含めることも、対称ペア {11} を含めることもできません。

より具体的には、上記の例で、最初のリストからアイテムのペア 14 を選択した場合、2 番目のリストの選択肢は 25 だけです。これは、14 と 15 に「1」が含まれているためです。したがって、16 と 17 には「1」が含まれ、25 と 26 には「2」が含まれるため、3 番目のリストからの唯一の選択肢は 36 です。

リストにはそれぞれ何百ものアイテムのペアが含まれている可能性があるため、選択肢のすべての順列を通過せずに「これは有効な選択ですか?」と尋ねることなく、アイテムのペアの合計組み合わせをカウントする効率的な方法を知っている人はいますか?

アップデート

これにしばらく時間を費やした後、どのリストも異なるペアを共有していない場合、組み合わせの数を数えるのは簡単であることに気付きました。ただし、異なるペアが 2 つ以上のリスト間で共有されるとすぐに、組み合わせ式は適用されません。

今のところ、すべてのリストに同じアイテムのペアがある組み合わせの数を数える方法があるかどうかを把握しようとしています (力ずくではなく組み合わせ数学を使用)。例えば：

1. {12,23,34,45,67}
2. {12,23,34,45,67}
3. {12,23,34,45,67}

私は 2,000 万人のユーザーのデータベースとそれらの人々の間のつながりを持っています。プログラミングで 最も効率的な方法で「6度の分離」の概念を証明するにはどうすればよいですか?

6度の分離に関する記事へのリンク

• 潜在的な読者の時間と健康を節約するために、元のテキストを編集しました。多分誰かがこれを実際に使用するでしょう。

私はそれが基本的なものであることを知っています。おそらく非常に基本的なものです。
指定されたセットのすべての可能な組み合わせを取得する方法。例
string set = "abc";
abc aa ab ac aaa aab aac aba abb
abc aca acb acc baa bab ...
そしてリストは続きます (長さの制限が設定されていない場合)。

そのための非常にきれいなコードを探しています-私が見つけたのは、ちょっと汚れていて正しく機能していませんでした。私が書いたコードについても同じことが言えます。

複数のスレッドで動作するブルート フォース (md5) 実装を作成しているため、このようなコードが必要です。パターンは、スレッドに独自の組み合わせのチャンクを供給する親プロセスがあるため、これらは独自に処理します。
例: 最初のスレッドは 100 個の順列のパッケージを取得し、2 番目のスレッドは次の 100 個を取得します
。最終的なプログラムをどこかに投稿する必要があるかどうか教えてください。

EDIT #2 もう一度、皆さんに感謝します。
あなたのおかげで、私は MPICH2 で実装されたスレーブ/マスター ブルート フォース アプリケーションを完成させました (そうです、Linux やネットワークなどの Windows で動作します)。時間 (そして太陽) 次のタスクに進みます ... :)
StackOverflow コミュニティが素晴らしいことを教えてくれました - ありがとう!

私は、各要素が元の場所とは異なる順列で作業しています。{入力の長さ、行、桁}を指定すると、出力番号が得られるアルゴリズムが必要です。次に例を示します。

入力長が4の場合、0123のすべての順列は次のとおりです。

同じ場所に数字がない（すべての数字が移動した）順列：

番号付けは0から始まるため、関数への入力が{4,0,0}の場合、出力は0番目（最初）の順列の0番目（左端）の桁になります。1032の最初の桁は1です。

入力が{4,1,1}の場合、出力は1230の2桁目である2です。

行番号は、順列の数よりも大きい場合があります。その場合、順列の数を法として余りを取ります（上記の場合、9を法とする行）。

C言語では素晴らしいでしょう。

（宿題ではなく、仕事用です。知っておく必要がある場合はカッコウのハッシュです。各段階で行うスワップをランダムに選択して、テーブルの数が2を超える場合にBFSよりも優れているかどうかを確認したいと思います。 。）

次のクラスの問題の名前を探しているので、効果的なアルゴリズムと詳細情報をグーグルで検索できます。

{-1, 0, 1} の 3 文字のアルファベットがあります。

長さ 24 のすべての文字列を効果的に生成する必要があります。これらのほとんどは {0} ですが、0 ～ 8 個の {1,-1} 文字が特定のパターンで分散されています。(パターンには、{-1} の数とペアリングに関する制限があります)。私の基準を満たす文字列の総数はかなり控えめで、約 128,000 です。

では、このクラスの問題/アルゴリズムの名前は何ですか?

少しScalaを学ぼうとすると、この問題に遭遇しました。ここで繰り返しのないすべての組み合わせの解決策を見つけました。その背後にある考え方はある程度理解していますが、構文の一部が混乱しています。また、ソリューションが繰り返しのあるケースには適していないと思います。誰かが私が作業できるコードを少し提案できるかどうか疑問に思っていました. 私は組み合わせ論に関する資料をたくさん持っており、問題とそれに対する反復的な解決策を理解しています。それを行うためのスケーラな方法を探しているだけです。

ありがとう

無線ノードのセットが互いに近接しており、重複を最小限に抑えるために周波数を割り当てたいと考えています。エリアを完全にカバーするには、無線チャネルをオーバーサブスクライブする必要があるため、近くの無線が同じ周波数で送信されます。

サンプルデータ:
5 周波数
343 ラジオ
4158 エッジ

私の現在の最良の推測は、周波数割り当ての母集団をランダムに生成し、最高のスコアが 10 世代にわたって改善されなくなるまで無線間で周波数を交換することです。スコアは、同じ周波数の無線の 1/range^2 の合計です。

各エッジは無線間の距離で、壁と床を補正したものです。最大無線距離の 2 倍を超えるエッジはリストから除外されています。

より良い方法はありますか？