Solved

Making combinations of elements in a hashmap

Posted on 2007-03-24
3
720 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
3 Comments
 
LVL 10

Expert Comment

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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

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

For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
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 will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

726 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