4

私は非常に奇妙な問題を抱えており、解決を困難にするいくつかの制約があります。リストのリストがあり、それらのリストのすべてのアイテムの組み合わせを実行したいと思います。各アイテムには名前と値があります。次に例を示します。

メインリスト：

  • リスト01：
    • アイテム01：名前：名前01、値：値01
    • アイテム02：名前：名前02、値：値02
  • リスト02：
    • アイテム01：名前：名前03、値：値03
  • リスト03：
    • アイテム01：名前：名前04、値：値04
    • アイテム02：名前：name05、値：value05

最終結果は次のようになります。

いくつかのリスト：

  • アイテム01：name01：value01、name03：value03、name04：value04
  • アイテム02：name02：value02、name03：value03、name04：value04
  • アイテム03：name03：value03、name03：value03、name04：value04
  • アイテム04：name01：value01、name03：value03、name04：value05
  • アイテム05：name02：value02、name03：value03、name04：value05
  • アイテム06：name03：value03、name03：value03、name04：value05

新しいリストには、ハッシュマップのように機能するアイテムがほとんど含まれています。

制約は次のとおりです。

  1. これらのリストはすぐに大きくなる可能性があるため、新しいリストにまとめてそれらを混在させることはできません。
  2. 私はある種のオブザーバーのようなAPIを使用しているので、多くのメモリを使用しないように、できるだけ早く結果についてオブザーバーに通知する必要があります。

言い換えると、この組み合わせジェネレーターにはX個のリストが供給され、各リストにはN個のアイテムが含まれる可能性があり、メモリをあまり使用せずにそれらの組み合わせを生成する必要があります。

一度に5つを超えるリストで作業することは期待していませんが、アルゴリズムをコードの変更に対して可能な限り回復力のあるものにしたいと思います。

私はJavaで問題を解決していますが、アルゴリズムは翻訳される可能性が高いため、他の言語でも同様に機能するはずです。

何かアイデアや提案はありますか？

前もって感謝します。

PS再帰がうまくいくとは思いません。whileループといくつかのネストされたループを使用するというアイデアをいじっていますが、これがどのように機能するかを想像するのは非常に困難になっています。

4

4 に答える 4

2

それで、これはデカルト積です、あなたは求めていますか？

2、1、3要素の3つのリストを想定します。2 * 1 *3の組み合わせ=6で終わります（要約：a * b * ... * i）

ここで、0から5までの6つの数字を取ります。

void getCombiFor (int i, List <List <Integer>> li) 
{
     if (li.length > 0) 
     { 
        int idx = i % li.get (0).size ();        
        System.out.print (li.get (0).get(idx));                 
        getCombiFor (i - idx, li.remove (0));
     } 
     System.out.println ();
}   
// pseudocodeline:
List li = List (List ('a', 'b'), List ('c'), List ('d', 'e', 'f'))
for (int i = 0; i < 6; ++i) 
{
     getCombiFor (i, li);
}

例：

Lists = ((a,b), (c), (d,e,f))
acd
bcd
acf
bcf
ace
bce
于 2011-02-17T01:52:49.803 に答える
1

この問題を解決するためにメモリを使用する必要はありません。組み合わせ全体を作成せずに、リストのN番目の要素を数学的に取得することができます。ここで説明します

于 2011-02-17T01:09:56.770 に答える
0

指定されたリストごとに1つずつ、インデックスの配列を作成するのはどうですか？現在の組み合わせは、各リストでget（）を順番に実行することで読み取ることができます。各インデックスはゼロになります-次に、実際に行う次の組み合わせに進みます

index[0]++;
if (index[0] >= list[0].size()) {
    index[0] = 0;
    index[1]++;
    if (index[1] >= list[1].size()) {
        ...
    }
}

（ネストされたifを、読者の演習として残された反復に変換します。）

于 2011-02-17T00:52:17.657 に答える
0

実際にハッシュマップを作ってみませんか？

Map<String,Map<String,String>> mainMap = new HashMap<String,Map<String,String>>();

for(List l : lists) {
    for(Data d : l) {
        String item = d.item;
        String name = d.name;
        String value = d.value;

        Map<String,String> itemMap = mainMap.get(item);
        if(item == null) {
            itemMap = new HashMap<String,String>(); 
            mainMap.put(item,itemMap);
        }
        itemMap.put(name,value);
    }
}

後で、どのアイテムに関係なく、指定された名前のすべての値を取得したいですか？

List<String> getValuesForName(String name) {
    List<String> list = new LinkedList<String>();
    for(Map<String,String map : mainMap) {
        String value = map.get(name);
        if(value != null) list.add(value);
    }
    return list;
}
于 2011-02-17T00:57:33.160 に答える