# 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();
for (int n = m; n < allCombinations.length; n++) {
if (!isSubString(uni, allCombinations[n])) {
}
}
if (checkForAllElements(allElements, uni)) {
if (!alradyCalculated(sumCombinations, 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 :-(
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
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--//

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)
{

//Only one possible combination for 'n', namely take the rest

//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--//
0
Author Commented:
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
0
Commented:
Oh, yeah i forgot to mention, but it uses a global array now, but that's not necessary of course. You just have to pass the element array to all the functions. So the function signatures are:

public static LinkedList<String> combinations(String[] allElements, int n, int offset)
public static String take(String[] allElements, int n, int offset)

Now every call to combinations and take should pass the allElements. So the call in the main function becomes:

combinations(allElements, allElements.length, 0);
etc.

I hope that it's clear how to continue from here. I included the source, just in case.

Also, if you are going to use this on very large string it might be better to use a StringBuffer with append() instead of String with + concatenation.

Mark
//--Combinations.java--//

public class Combinations
{
//Make combinations for a (sub)list of length 'n'
public static LinkedList<String> combinations(String[] allElements, int n, int offset)
{

//Only one possible combination for 'n', namely take the rest

//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(allElements, n-i, offset);

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

return result;
}

//Concat 'n' elements from list starting from an 'offset'
public static String take(String[] allElements, 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)
{
String[] allElements = new String[]{"A", "B", "C", "D"};
LinkedList<String> result = combinations(allElements, allElements.length, 0);

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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.