Solved

# Making combinations of elements in a hashmap

Posted on 2007-03-24
Medium Priority
730 Views
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)) {
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 :-(
0
Question by:dr_alinaeem
• 2

LVL 10

Expert Comment

ID: 18788093
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)))
}

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

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

Author Comment

ID: 18788605
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:
//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

LVL 10

Accepted Solution

ID: 18788624
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)))
}

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

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
How to fix incompatible JVM issue while installing Eclipse While installing Eclipse in windows, got one error like above and unable to proceed with the installation. This video describes how to successfully install Eclipse. How to solve incompa…
###### Suggested Courses
Course of the Month15 days, 15 hours left to enroll