algorithm - Java Combinations of elements of Map<A, List<B>> -

(ps. rewrote question thought dealing permutations, dealing combinations.)

consider more map<string, list<wordgroupandscore> basemap, with:

private static class wordgroupandscore {     public final wordgroup wordgroup;     public final int score;      public wordgroupandscore(final wordgroup wordgroup, final int score) {         this.wordgroup = wordgroup;         this.score = score;     } } 

the basemap.size() variable, meaning there can number of strings in map. every element in basemap, basemap.get(i).size() variable. basemap cannot contain empty lists.

now trying find possible combinations. code checking data in invoices, not data available on invoice, hence variable amount of basemap.size(). , list per element in basemap variable, because amount of data found depends on invoice is.

(example data not correspond 1 one in example, in reality wordgroupandscore, i'll use strings or bigdecimals represent data in example)

example data of basemap (values , key pairs) strictly (a , list<b> pairs):

• ("invoicenumber", ["0001", "0002"])
• ("invoicedate", ["2013-10-07"])
• ("priceexclvat, [new bigdecimal("10.00")])
• ("highvat, [new bigdecimal("2.10")])
• ("priceinclvat, [new bigdecimal("12.10"), new bigdecimal("14.10")])

i want generate possible combinations of data.

example output, 1 ("first") combination (values , single key pairs) strictly (a , b pairs):

• ("invoicenumber", "0001")
• ("invoicedate", "2013-10-07"])
• ("priceexclvat, new bigdecimal("10.00"))
• ("highvat, new bigdecimal("2.10"))
• ("priceinclvat, new bigdecimal("12.10"))

example output, 1 ("last") combination (values , single key pairs) strictly (a , b pairs):

• ("invoicenumber", "0002")
• ("invoicedate", "2013-10-07")
• ("priceexclvat, new bigdecimal("10.00"))
• ("highvat, new bigdecimal("2.10"))
• ("priceinclvat, new bigdecimal("14.10"))

so somehow need iterate on full basemap, remember/create combinations based on every basemap.get(i).size(), pretty lost start. biggest problem that: how remember combinations, because basemap of variable size. if not have been variable, could've done easier.

i hope question clear enough.

edit: added 1 of tries, doesn't work.

//assumes wordgroupsandscores not changed during process private void processwordgroupandscores(templatebean template) {     system.out.println();     system.out.println("--wordgroupsandscores--");     (map.entry<string, list<wordgroupandscore>> entry : wordgroupsandscores.entryset()) {         system.out.println("attribute = " + entry.getkey());         (wordgroupandscore wordgroupandscore : entry.getvalue()) {             system.out.println("wordgroupandscore = " + wordgroupandscore);         }         system.out.println(";");     }     system.out.println();     //create possible unfinishedinvoices wordgroupandscores     int[] indices = new int[wordgroupsandscores.keyset().size()];     (int index = 0; index < indices.length; index++) {         indices[index] = 0;     }     string[] keylocation = new string[wordgroupsandscores.keyset().size()];     int j = 0;     (string key : wordgroupsandscores.keyset()) {         keylocation[j] = key;         j++;     }     processwordgroupandscoresrecursive(indices, keylocation, template); }  private void processwordgroupandscoresrecursive(int[] indices, string[] keylocation, templatebean template) {     processwordgroupandscoreswithindices(indices, keylocation, template);     boolean changedindices = false;     (int index = indices.length - 1; index >= 0; index--) {         if (indices[index] < wordgroupsandscores.get(keylocation[index]).size() - 1) {             indices[index]++;             changedindices = true;             break;         }     }     if (changedindices) {         processwordgroupandscoresrecursive(indices, keylocation, template);     } }  private void processwordgroupandscoreswithindices(int[] indices, string[] keylocation, templatebean template) {     system.out.println();     system.out.println("--generated combination--");     unfinishedinvoice unfinishedinvoice = new unfinishedinvoice();     (int index = 0; index < indices.length; index++) {         string key = keylocation[index];         wordgroupandscore wordgroupandscore = wordgroupsandscores.get(key).get(indices[index]);         system.out.println("attribute = " + key);         system.out.println("wordgroupandscore = " + wordgroupandscore);         system.out.println(";");         setunfinishedinvoiceattribute(key, unfinishedinvoice, utils.joinwordgroup(wordgroupandscore.wordgroup, " "), wordgroupandscore.score);     }     system.out.println();     unfinishedinvoice.verify();     if (templatemap.containskey(template)) {         templatemap.get(template).add(unfinishedinvoice);     }     else {         list<unfinishedinvoice> list = new arraylist<>();         list.add(unfinishedinvoice);         templatemap.put(template, list);     } } 

let's take more clear @ produces, let work indices, , not real data anymore.

let's input: [1, 1, 2, 1, 0]. being characterization of map list, elements index of element in lists inside original map. start combination last elements map being taken.

with failing code output:

• [1, 1, 2, 1, 0]
• [1, 1, 2, 0, 0]
• [1, 1, 1, 0, 0]
• [1, 1, 0, 0, 0]
• [1, 0, 0, 0, 0]
• [0, 0, 0, 0, 0]

this not correct there lot of values missing, example [0, 0, 0, 1, 0] missing.

what going wrong here?

sample pseudo-code using recursive function. each level of recursion processes 1 list taking elements 1 one, putting them in output variable , recursively calling process next iteration level.

void allcombinations(map<a, list<b>> input, map<a, b> output){    if (input not empty){       (x, y) = input.removeoneelement(); //removes 1 list input       each b in y{         output.insert(x, b);             //adds element output         allcombinations(input, output);  //recursively calls         output.remove(x, b);             //removes element output       }    }else{       print(output)                      //here print output    } } 

so creates sizeof(input) nested loops using recursion.

you call using:

allcombinations(input, new map<a, b>()); 

note: if instead of printing output want returned. change signature of method:

void allcombinations(map<a, list<b>> input, map<a, b> output, list<map<a,b>> result) ... result.add(output); //instead of print(output); 

and call using:

list<map<a,b>> result = new list<map<a,b>>(); allcombinations(input, new map<a, b>(), result);