0

似たような質問がたくさんあることは知っており、何時間も読んでいます。しかし、どれも私の要件を満たしていないようです。

リストのリスト ( list< list < string > >) があります。リストは任意のサイズにすることができます。

例：

私の外側のリストのサイズは: 4

リストの内容

 1. list(0) a,b,c            &nbsp; &nbsp; &nbsp; &nbsp; size:3

 2. list(1) d,b,f,m          &nbsp; &nbsp; &nbsp; size:4

 3. list(2) x,a              &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  size:2

 4. list(3) b,e,d,m,a        &nbsp; &nbsp; size:5

ここに私の組み合わせがあります

adxb

adxe 

adxd (adx) duplicate element will be removed after generating combination

adxm

adxa (adx)  

adab (adb)

adae (ade)

...

...すぐ

各リストから 1 つの要素を選択して組み合わせを生成する必要があります。組み合わせの長さは最大 4 (外側のリストのサイズ) になります。組み合わせで同じ要素を取得すると、縮小される場合があります。

私の組み合わせの数は、各内部リストの要素数の積​​になります。

上記の例では、組み合わせの数は組み合わせになり3x4x2x5=120ます

私のリストには重複した要素が含まれているため、adab adba がある場合、ここでも重複した組み合わせが得られます。順序は重要ではないため、 adbaは重複しています。

問題は、単純なアプローチを使用して組み合わせを生成することです。外側のリストのサイズが大きくなり、内側のリストにさらに多くの要素が含まれている場合、何百万もの組み合わせを生成することになりますが、1000 または 2000 のみが一意で残りはすべて重複します。

すべての組み合わせを生成する代わりに、一意の組み合わせのみを生成するアルゴリズム的アプローチはありますか?

4

2 に答える 2

1

1: これは宿題ですか?
2: 最大でいくつのリストを使用すると予想されますか?

基本的に...これを行うための魔法のような方法はありません...作成中の文字列に、追加を検討している文字が既に含まれているかどうかを確認する必要があります。最適化したい - 文字列にすでに文字が含まれているかどうかを確認します。

宿題のためにこれを行っている場合は、 String.contains( 'a' ) || を使用できると思います。String.contains( 'A' ) を使用して、文字列に特定の文字 (この場合は 'a') が既に含まれているかどうかを確認します。あとはお任せします。これは O(n^2) 操作であることに注意してください。

これをより... 工業的な... アプリケーションで行う場合は、別のオプションがあります。

多数の文字列リストを作成する場合は、既に使用した文字のリストを格納するために TreeSet を使用することをお勧めします。たとえば、最初のリスト (a、b、c) を調べた後、「使用文字」の TreeSet に「a」が含まれているかどうかを確認し、含まれていない場合は、文字列に「a」を追加します。構築し、使用する文字の TreeSet に「a」を追加します。次に、2 番目のリストに移動し、TreeSet に文字 d が含まれているかどうかを確認します。全体として、これは o(n*log(n)) 関数になります。

TreeSet を使用して「使用済み」文字のリストを格納する利点は、文字列を使用して文字列内の文字をチェックする o(n) とは対照的に、文字を追加してチェックするのに o(log(n)) がかかることです。含む ("a")。(追加/チェックする前に、すべてを小文字に変換することもできます。)

TreeSet を使用することの欠点は、TreeSet をインスタンス化するだけで適度な量のオーバーヘッドが発生することです。文字列リストの小さなリストのみを使用している場合は、その価値がない可能性があります。

質問: 文字のリストのリストではなく、文字列のリストのリストがあるのはなぜですか? 文字のリストのリストがより適切であるように思われます。

o(n^2)、o(log(n))、または o(n) の意味に慣れていない場合、o(whatever) は、関数の実行時間がどのように拡張されるかを概算するための単なる表記です。その関数に渡される引数の数。
-たとえば、4 つの引数で o(n^2) 関数を実行すると、4^2 == 16 時間かかります (「時間」は任意の時間単位です)。8 つの引数で実行すると、8^2 == 64 時間かかります。入力サイズが大きくなるにつれて、二次的に増加します。
-たとえば、4 つの引数で o(n) 関数を実行すると、4 回実行されます。8 つの引数で o(n) 関数を実行すると、8 時間かかります。
-たとえば、4 つの引数で o(log(n)) 関数を実行すると、2 時間かかります。8 つの引数で o(log(n)) 関数を実行すると、3 時間かかります。(対数が底 2 であると仮定します。

うまくいけば、アイデアが得られます-ポイントは、o(n^2)、o(n*log(n))、o(n)、および o(log(n)) の違いは小さな数値では小さいということです。しかし、サイズが 100 以上のリストを取得し始めるとすぐに、それは重要になります -- o(n^2) は 10,000 時間かかり、o(n*log(n)) は 670 時間程度かかります -- それはつまり、100 個のリストだけで 15 倍速くなります。リスト数が 1,000 になると、100 倍速くなります。

于 2013-06-03T07:01:44.560 に答える