2
\$\begingroup\$

Print all combinations from dictionary which will result in the number N

   Input:
            
          Dictionary { “flag”:4.5, “temp”:2 ,”foo”:9} and N = 11
    
   Output:
               temp*1+flag*2
               flag*2+temp*1
               foo*1+temp*1
               temp*1+foo*1

code:

public class CombinationsofDictionary {

    // static for convenience of debugging
    public static void printCombinations(HashMap<String,Float> map,float n){

        Set<String> results = new HashSet<>();


        for(Map.Entry<String,Float> entry: map.entrySet()){

            //calculate all possible results which are valid(>0)
            HashMap<Integer,Float> sums = new HashMap<>();

            float result = n - entry.getValue();
            int factor = 1;
            while(result >= 0 ){
                sums.put(factor,result);
                factor++;
                result -= entry.getValue();
            }

            //nested for loop on the same map
            for(Map.Entry<String,Float> entry2: map.entrySet()){

                if(!Strings.equals(entry.getKey(),entry2.getKey())) {
                    for (Map.Entry<Integer,Float> f : sums.entrySet()) {

                        float res = f.getValue() / entry2.getValue();

                        //if res is an integer we have found the match.
                        if (res == Math.round(res) && res > 0) {

                            // to build a string without concatination.
                            StringBuilder sb = new StringBuilder();
                            sb.append(entry2.getKey());
                            sb.append("*");
                            sb.append(String.valueOf(Math.round(res)));
                            sb.append("+");
                            sb.append(entry.getKey());
                            sb.append( "*");
                            sb.append(String.valueOf(f.getKey()));

                            results.add(sb.toString());
                        }
                    }
                }
            }



        }


        for(String rString : results){
            System.out.println(rString);
        }


    }

    public static void main(String...args){

        HashMap<String,Float> values = new HashMap<>();
        values.put("flag", 4.5f);
        values.put("temp", 2f);
        values.put("foo", 9f);

        printCombinations(values,11);
    }
}

This solution is O(n^2) in time. The code looks nasty but I am not sure how to make it look good. Also looking for a better solution in linear time(if possible?).

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Orderings are not considered in combinations. temp*1 + flag*2 and flag*2 + temp*1 would be considered the same combination. Permutations are ordering dependent. Perhaps you meant “print all permutations …”? \$\endgroup\$
    – AJNeufeld
    Jun 14 at 14:11
  • 1
    \$\begingroup\$ What are the problem constraints? There would be an infinite number of combinations that could result in the sums. 4*flag + 1*temp + (-1)*foo, 6*flag + 1*temp + (-2)*foo, and so on. Can the dictionary contain a term with value 0? \$\endgroup\$
    – AJNeufeld
    Jun 14 at 14:16
  • \$\begingroup\$ Sorry for the confusion, yes it should be "print all permutations" and the multiplying factors are positive integer values only and only two terms of the dictionary should be present in every solution. \$\endgroup\$ Jun 14 at 17:33
  • \$\begingroup\$ Consider the worst case: all values are 1. Every pair of values, \$n^2\$ of them, gives \$N\$ solutions. Since you have to print all of them (rather than enumerate) do not expect a time complexity less than \$O(N n^2)\$. \$\endgroup\$
    – vnp
    Jun 14 at 21:24
  • \$\begingroup\$ hmm I see your point. Makes sense.I guess my question is would it be possible to iterate over the dictionary twice instead of a nested loop. \$\endgroup\$ Jun 14 at 22:15
3
\$\begingroup\$

I'm picking up your point: The code looks nasty but I am not sure how to make it look good.

if you are using java it's recommended to write code in object-orientated manner. Doing so will clean up (and bloat) the code, hopefully it finally leads to an SOLID code ;-)

one Step would to create methods

you have already identified methods, so instead of writing comments write methods, like here:

for(Map.Entry<String,Float> entry: map.entrySet()){

    //calculate all possible results which are valid(>0)
    HashMap<Integer,Float> sums = new HashMap<>();

    float result = n - entry.getValue();
    int factor = 1;
    while(result >= 0 ){
        sums.put(factor,result);
        factor++;
        result -= entry.getValue();
    }
    ...
}

after extracting a method;

for(Map.Entry<String,Float> entry: map.entrySet()){
    HashMap<Integer,Float> sums = calculatePossibleResults(entry);
    ...
}

or here to name another example

//if res is an integer we have found the match.
if (res == Math.round(res) && res > 0) {

    // to build a string without concatination.
    StringBuilder sb = new StringBuilder();
    sb.append(entry2.getKey());
    sb.append("*");
    sb.append(String.valueOf(Math.round(res)));
    sb.append("+");
    sb.append(entry.getKey());
    sb.append( "*");
    sb.append(String.valueOf(f.getKey()));

    results.add(sb.toString());
}

could also be extracted:

if (isInteger(res)) {
    results.add(createPermutationOutput(entry2, entry, res);
}

also this method if(!Strings.equals(entry.getKey(),entry2.getKey())) could be namend properly: if(entriesDiffer(entry, entry2))

one other step would be better variable naming

float n - well i know its from your assesment, but you still could use a proper name... float desiredPermutationResult? sounds like an overkill on your Keyboard? but most IDE support autoFilling so no prob ^^

HashMap<Integer,Float> sums = new HashMap<>(); should have the proper name: HashMap<Integer,Float> candidates = new HashMap<>(); (see your own comment! : calculate all possible results which are valid(>0))

next step would be to create Objects

instead of using primitve data types Map<String,double> you could use data objects that represent them. that would lead to a more readable code. Candidates would be

class Dictionary that provides a method calculatePermutations(float n) maybe a class PermutationPrinter that would handle the proper printing?

Dictionary dictionary = new Dictionary();
Permutations permutations = dictinary.getPermutations();
PermutationsPrinter printer = new PermutationsPrinter();
printer.print(permutations);

doing so you could...

  • easily change how the content of the dictionary is filled.
  • you could easily adjust print
  • you could use your outcome on other applications

and all code is on that part, where it belongs - so anyone who will ever read your code would know what these things do and how they work

tests (as part of an oop-approach)

it might help to write test to verify the behaviour of your code. if you have objects you can easily test the desired behaviour in a clean seperate test (e.g. it would be easy to test the printer, even though you don't yet have the algorithm solved)

assets

since this work looks like it's an asset from your teacher or LeetCode or similar... these assests only pick one aspect of coding, it's most like the math part - but there are other factors to consider, like using oop-approach to create solid code ;-) these traits are mostly not considered in these assests

\$\endgroup\$
1
\$\begingroup\$

I don't think the code prints all the combinations. It only prints combinations of two dictionary pairs. I ran the code and it prints:

Input:    
          Dictionary { “flag”:3, “temp”:2 ,”foo”:4} and N = 12
Output:
          foo*1+temp*4
          flag*2+temp*3
          temp*3+flag*2
          foo*2+temp*2
          temp*4+foo*1
          temp*2+foo*2

I wrote this code, it prints all the combinations, it is in C# though :)

class MainClass
{
    static List<List<string>> formulas;
    public static void Main (string[] args)
    {
        Dictionary<String, float> dic = new Dictionary<string, float>();
        dic.Add("flag", 4.5f);
        dic.Add("temp", 2f);
        dic.Add("foo", 9f);

        int target = 11;

        List<float> values = new List<float>();
        List<string> keys = new List<string>();

        // combination is a list of key/factor pairs that their sum equals target.
        // e.g. a combination for target = 12 [{flag,2},{temp,3}]
        // another combination [{foo,1},{flag,2},{temp,1}]
        var comb = new List<Tuple<int,int>> ();

        foreach (var kvp in dic) {
            values.Add (kvp.Value);
            keys.Add (kvp.Key);
        }

        // formulas is a list of combinations that equals to target;
        // e.g. formuals = [ [flag*2,temp*3], [foo*1,flag*2,temp*1],...etc ]
        formulas = new List<List<string>> ();

        solve (0, 0, comb, target, values, keys, dic.Count);

        // get all permutations of each formula.
        foreach(var l in formulas){
            permutation (0, l, l.Count);
        }

        Console.ReadKey ();
    }

    private static void permutation(int start, List<string> list, int n){
        if (start == n) {
            // print
            string p = "";
            foreach(string s in list){
                p = p + s + "+";
            }
            p = p.Substring (0, p.Length - 1);
            Console.WriteLine (p);
            return;
        }

        for (int i = start; i < list.Count; ++i) {
            // swap
            string temp = list[i];
            list [i] = list [start];
            list [start] = temp;

            permutation (start + 1, list, n);

            // backtrack swap
            string temp2 = list[i];
            list [i] = list [start];
            list [start] = temp2;
        }
    }

    private static void solve(int start, float sum, List<Tuple<int,int>> combination, int target, List<float> values, List<string> keys, int n){
        if (start == n) {
            if (sum == target) {
                // store the this combination in answer.
                var l = new List<string> ();

                foreach (var tup in combination) {
                    if(tup.Item2 != 0)
                        l.Add (keys[tup.Item1] + "*" + tup.Item2);
                }
                formulas.Add (l);   
            }
            return;
        }

        int f = 0;
        while (true) {
            float x = values [start] * f;

            if (x + sum > target)
                break;

            combination.Add (Tuple.Create (start, f));
            solve (start + 1, x + sum, combination, target, values, keys, n);
            combination.RemoveAt (combination.Count - 1);

            ++f;
        }
    }
}

The output is:

"foo*3
temp*2+foo*2
foo*2+temp*2
temp*4+foo*1
foo*1+temp*4
temp*6
flag*2+temp*1+foo*1
flag*2+foo*1+temp*1
temp*1+flag*2+foo*1
temp*1+foo*1+flag*2
foo*1+temp*1+flag*2
foo*1+flag*2+temp*1
flag*2+temp*3
temp*3+flag*2
flag*4
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.