問題タブ [powerset]

文字列のサブセットを見つけるための Java メソッドを作成しようとしていますが、デバッグできなかったランタイム エラーが発生し続けます。コードは次のとおりです。

こんにちは、私はすでにフォーラムを見ましたが、私の問題に対する解決策が見つかりませんでした。問題は、Sサイズのリストのすべての可能なサブセット[長さl]をどのように見つけることができるかです。そしてそれをリストで返します。

更新: @bphelpsjr の回答は、私が探しているものを提供します。残念ながら、誰かが彼に反対票を投じましたが、私には賛成票を投じる担当者がいません。私は彼の反応を答えとしてマークしています。

これは非常に長くなりましたが、できるだけ詳細を提供したかったのです。

基本的に、一連のデータを取得し、ルール (以下で定義) に基づいてリストのリストを生成したいと考えています。これは基本的に、パワーセットのフィルター処理されたバージョンです。

次に、これらの結果を繰り返し使用するために保存し (レインボー テーブルの場合と同様)、同じ が常に計算されるのを回避しNます。次に、他のロジックを適用する前に、変数置換 (たとえば、A = 18、B = 30) を使用します (以下では説明しません。私の質問には必要ありません)。

ソリューションを作成するために実験した 2 つの入力オプションを次に示します。文字の代わりに数字を使用することもできます。

入力オプション #1

入力オプション #2

望ましい出力

ルール

最初の 3 つは決定的なルールですが、4 番目はもっと欲求です。

1. ソリューションは、 N個の個別の文字と項目のリストを処理できなければなりません

2. すべての個別の文字は、アイテムのリストに少なくとも 1 回表示される必要があります。例：

   AA BB CC DD <-- 有効

   AA BB CC <-- 無効、D を含まない

3. 文字は、特定のアイテム内でのみ繰り返すことができます。例：

   AA BB CC DD <-- 有効

   AA BA CC DD <-- 無効、A は別の項目で繰り返されます

4. 実行する反復回数を減らすために、ロジックにはできるだけ多くの「アグレッシブ フィルタリング」とショート サーキットを含める必要があります。私は機能する左シフト ソリューションを持っていましたが、(私の?) フィルタリングと短絡を組み込むことができないため、まったく拡張できません。これにより、基本的に、パワーセット全体を反復処理することになりました。

   • 例: 可能性のあるリストの項目に既に含まれている文字が見つかったら、これは無効であるため、次の可能性のある組み合わせに進みます。

   • 例: アイテムの有効なリストが見つかったら、次のラウンドを開始します。

次の 2 つは、各項目の最初の文字でグループ化されたデータ セットを現在持っている方法に基づく潜在的な例です。作成するソリューションの種類によっては、適用できない場合があります。

• 考えられる例: 項目に次のリストの項目にある文字が含まれている場合、そのリスト全体をスキップして次の項目のリストに移動します。

  AA BC DD <-- C リストは BC でカバ​​ーされているためスキップできます

• 潜在的な例: リストの潜在的な候補を使い果たしたら (たとえば、最後のリストには 1 つのアイテムしかない)、(私の考えが正しければ) 上のリスト + 1 がアイテムを変更するまで、そのリストを再度必要とするべきではありません。 .

  AA BB CC DD <-- これを見つけたら、BC (DD + 1 の上のリスト) に到達するまで、DD を含むリストの検索を停止します。

  AA BB CD

  AA BC DD <-- また DD が必要

  1. 項目の順序に関係なく、項目のリストが繰り返されることはありません。例：

  AA BB CC DD == BB AA DD CC なので、BB AA DD CC は含めないでください。

私が行った仮定：

• 最初の開始文字でセットをグループ化する方が簡単です (以下のサンプル データを参照)。これが最適なアプローチでなくても問題ありません。

以下は、便宜上、データを保持するために使用する Item クラスです。

グラフ内のノード要素のリストのパワーセットを生成しようとしています。以前の投稿 (セットのユニークな組み合わせ)から次のコードを特定して適応させました。

を使用して機能をテストしています

ただし、PowerSet 関数の関数 (a,b) を指す無効なキャスト例外エラーが発生します。

追加情報: タイプ 'WhereSelectListIterator 2[System.Collections.Generic.List1[cDAG_with_classes.Node],System.Collections.Generic.IEnumerable 1[cDAG_with_classes.Node]]' to type 'System.Collections.Generic.IEnumerable1[System.Collections.Generic.List`1[cDAG_with_classes.Node]]' のオブジェクトをキャストできません。

私が間違っている可能性がある場所について、誰かアドバイスをいただけますか?

ありがとう

{'1','2','3','4'} などのセットのカスタム セットを生成できる単純な Java プログラムが必要です。結果は次のようになります: {'1','2'},{'2','3'},{'3','4'},{'1','2','3'},{ '2','3','4'}.

powerset のコードを試しましたが、出力が望ましくありません。コードが次のようなものである場合、それはかなりの価値があります。

.size() は ArrayList 用であり、 a[i] は単純な配列用であり、どのアプローチでも行うように両方を記述しました!! 前もって感謝します！！:)

次の文字列を検討してください

このように2文字順列（デカルト積）を返すことができます

ただし、次のような冗長なエントリを削除したいと思います

および無効なエントリ

だから私は残っています

例

私は面接のために勉強していて、オンラインの「数学」カテゴリでこの質問を見つけました。

指定されたセットのべき乗セットを生成します。

明確な答えは望まないでください。この問題に取り組む方法についての説明とヒントが欲しいだけです。

Google でパワー セット アルゴリズムを確認しましたが、この問題に対処する方法がまだわかりません。

また、誰かが質問が求めていることを繰り返してもらえますか.

ありがとうございました。