Solved

Making combinations of elements in a hashmap

Posted on 2007-03-24
3
678 Views
Last Modified: 2008-01-09
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 :-(
0
Comment
Question by:dr_alinaeem
  • 2
3 Comments
 
LVL 10

Expert Comment

by:ADSLMark
Comment Utility
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--//
0
 

Author Comment

by:dr_alinaeem
Comment Utility
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
 
LVL 10

Accepted Solution

by:
ADSLMark earned 100 total points
Comment Utility
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--//
import java.util.LinkedList;

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

        //Only one possible combination for 'n', namely take the rest
        result.add(take(allElements, 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(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

Featured Post

Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Issues installing SSL certificate into Apache Tomcat 3 70
changeXy challenge 13 56
computer science syllabus 3 52
Java and GPO 11 45
An old method to applying the Singleton pattern in your Java code is to check if a static instance, defined in the same class that needs to be instantiated once and only once, is null and then create a new instance; otherwise, the pre-existing insta…
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
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…

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now