asked on

Making combinations of elements in a hashmap

This is the final element of my simulator program, my program has reached a state where it gets a word splits into different segments for example ABC to A, AB, ABC, B, BC and C. My program then does calculations with each segment and assigns values to these segments and these are stored in a hashmap (as shown below).

***The code below runs in a loop, where segment is values from an array which stores the segments, I have just shown a code snippets, so you have an idea of how I have used the hashmaps***

HashMap<String, Double> result = new HashMap<String, Double>();
result.put(segment, new Double(sum));
Set<Map.Entry<String, Double>> set = result.entrySet();

for (Map.Entry<String, Double> me : set) {
System.out.print(me.getKey() + ": ");
System.out.println(me.getValue());
}

So at the moment my program gives an output as shown below:
A : 1.2
AB : 1.5
ABC : 1.6
B : 1.2
BC : 1.5
C : 1.3

The problem that I am having is trying to make all the possible unique combinations of the elements in the hashmap, for example,
A + B + C = 1.7
AB + C= 2.8
A+ BC= 2.7
ABC= 1.6
Above are all the possible combinations, however I cannot have a combinations which has repeat letters, for example: A+AB+C.

I was given the following solution below from expert-exchange, it works for a combination ABC, and any other combinations with unique characters, but it does not work for ABA (whixh has a repeated char). The code is below with ABA as the string in question.

import java.util.*;
import java.lang.*;

public class Combinations {

public static void main(String[] argv) {

String[] allElements = new String[] {"A", "B", "A"};
String[] allCombinations = new String []{"A","AB", "ABA", "B", "BA", "A"};
//NOTE: allElements and allCombinations are initialized like this only for
//test reasons
List sumCombinations = new ArrayList();
List uni = null;
for (int i = 0; i < allCombinations.length ; i++) {
for (int m = i + 1 ;m < allCombinations.length; m++) {
uni = new ArrayList();
uni.add(allCombinations[i]);
for (int n = m; n < allCombinations.length; n++) {
if (!isSubString(uni, allCombinations[n])) {
uni.add(allCombinations[n]);
}
}
if (checkForAllElements(allElements, uni)) {
if (!alradyCalculated(sumCombinations, uni)) {
sumCombinations.add (uni);
printArray(uni);
}
}
}
}
}

private static boolean alradyCalculated(List sumABC, List uni) {
boolean res = false;
for (Iterator iter = sumABC.iterator(); iter.hasNext();) {
List listElement = (List) iter.next();
if (compareLists(listElement, uni)) {
res = true;
}
}
return res;
}

private static boolean compareLists(List listElement, List uni) {
boolean res = true;
int cnt1 = listElement.size();
int cnt2 = uni.size();
if (cnt1 == cnt2) {
Iterator iter2 = listElement.iterator();
for (Iterator iter = uni.iterator(); iter.hasNext () && iter2.hasNext();) {
String stringElement1 = (String) iter.next();
String stringElement2 = (String) iter2.next();
if (!stringElement1.equals(stringElement2)) {
res = false;
}
}

} else {
res = false;
}
return res;
}

private static boolean checkForAllElements(String[] allElements, List uni) {
boolean res = true;
int numElements = allElements.length;
for(int i = 0; i< numElements; i++) {
if (!isSubString(uni, allElements[i])) {
res = false;
}
}
return res;
}

private static void printArray(List uni) {
System.out.print("* ");
for (Iterator iter = uni.iterator(); iter.hasNext();) {
String element = (String) iter.next();
System.out.print(element + ",");
}
System.out.println();

}

private static boolean isSubString(List uni, String patternString) {
boolean res = false;
for (Iterator iter = uni.iterator(); iter.hasNext();) {
String testString = (String) iter.next();
if (hasAnyCharacter(testString, patternString)) {
res = true;
}
}
return res;
}

private static boolean hasAnyCharacter(String testString, String patternString) {
boolean res = false;
for (int i = 0; i < testString.length(); i++) {
for (int j = 0; j < patternString.length(); j++)
if (testString.charAt(i) == patternString.charAt(j)) {
res = true;
}
}
return res;
}
}

The expected output should be:
* A,B,A,
* A,BA,
* AB,A,
* ABA,
But I am getting something else :-(

ADSLMark

I hope this works for you. It is a recursive definition of the problem you stated. It does not depend on the content of the element array, so it should be fine. I wasn't quite sure if you meant this, but the output seems to be what you want.
Small explanation (although it is also in comments):
You have to make combinations for n elements. You start out with n equal the number of elements in your array. Next we take the first n elements and form a string (step 1). Next we only take the n-1 elements from the array and call the combination function recursive on the rest (1 in this case). We continue with n-2, n-3 etc.
The last step after each round is to combine these results with the prefix and return the new result set.

Well have a look at the code, might be more clear then this vague explanation. :-)

Mark
//--Combinations.java--//
import java.util.LinkedList;

public class Combinations
{
private final static String[] allElements = new String[]{"A", "B", "C", "D"};

//Make combinations for a (sub)list of length 'n'
public static LinkedList<String> combinations(int n, int offset)
{
LinkedList<String> result = new LinkedList<String>();

//Only one possible combination for 'n', namely take the rest
result.add(take(n, offset));

//As long as we haven't reached 'n', combine to form new combinations
for(int i=1;i<n;i++)
{
//Take 'n-i' starting from the 'offset'
String prefix = take(n-i, offset);

//There are 'i' left to be taken, do these recursive
//Combine recursive results with 'prefix'
for(String rec : combinations(i, offset+(n-i)))
result.add(prefix + "-" + rec);
}

return result;
}

//Concat 'n' elements from list starting from an 'offset'
public static String take(int n, int offset)
{
String res = "";
for(int i=offset;i<offset+n;i++)
res += allElements[i];
return res;
}

//Calculate all combinations for 'allElements'
public static void main(String[] argv)
{
LinkedList<String> result = combinations(allElements.length, 0);

//Print results
for(String r : result)
System.out.println(r);
}
}
//--end Combinations.java--//

dr_alinaeem

ASKER

Thanks, seems to work how it should. However I am trying to intergrate this into my program which already has an array called allElements. So I am not adding private final static String[] allElements = new String[]{"A", "B", "C", "D"}; to my program, but this does not seem to work, I have also put the following code in my program's public static void main:
LinkedList<String> result = combinations(allElements.length, 0);
//Print results
for(String r : result)
System.out.println(r);
Thankyou for all ur help, I am increasing the points on guidance on how to make this work within my simulator

ASKER CERTIFIED SOLUTION

ADSLMark

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial