Create all combinations of mappings of characters to truth values

Question

I have a set of characters {'p', 'q', 'r', ...} and I want to call run() (not important what that does) on all permutations of mappings from the characters to boolean values. For example, if my set of characters was {'p','q','r'} and I naively went through every permutation manually, it would look like this:

private static void runMaps(){
    HashMap<Character,Boolean> m = new HashMap<>();
    m.put('p', true);
    m.put('q', true);
    m.put('r', true);
    run(m);

    m = new HashMap<>();
    m.put('p', true);
    m.put('q', true);
    m.put('r', false);
    run(m);

    // ...
    // 8 permutations
}

It's bugging me because I know I can (and should be able to) use recursion here but I'm struggling.

Edit: After a while I managed to get it working. There's some added stuff in the code below but the general idea is shown.

private static boolean runMaps(SyntaxTree formula, ArrayList<String> chars, HashMap<String, Boolean> map, int index) {

if (index == chars.size()) {
    return checkFormula(formula, map).getData().equals("true");
} else {
    HashMap<String, Boolean> newMap1 = (HashMap<String, Boolean>) map.clone();
    newMap1.put(chars.get(index), true);
    HashMap<String, Boolean> newMap2 = (HashMap<String, Boolean>) map.clone();
    newMap2.put(chars.get(index), false);
    return runMaps(formula, chars, newMap1, index + 1) && runMaps(formula, chars, newMap2, index + 1);
}

}

Well step one, you probably shouldn't be using a HashMap. HashMaps don't have order and a permutation is an ordering of elements so the two are incompatible. A LinkedHashMap would be a map structure with order typically matching the order of insertion. Second, look up on Google "permutation generation" to find some algorithms on how to generate permutations. Here's another stack overflow with how to generate permutations http://stackoverflow.com/questions/2710713/algorithm-to-generate-all-possible-permutations-of-a-list — FriedSaucePots, Aug 07 '15 at 21:21
Thanks for the tips. I don't need order in the sense that you are referring to - I only need to know e.g. whether p is true/false. I managed to get working after a while - I probably should have tried harder before posting here! — mmgro27, Aug 08 '15 at 00:00

score 0 · Answer 1 · answered Aug 07 '15 at 23:15

The basic concept would be to go through the map in some order, and then just divide it up, changing one character at a time.

something like this in pseudo code:

    Character[] keys = map.getKeys() // or something similar sounding
    int length = keys.length
    int position = 0

    function(keys, position, length, map) {
            if position >= length
                    return
            map.put(keys[position], false) // run all permutations with 0 in front
            function(keys, position+1, length, map)
            run(map)

            map.put(keys[position], right) // run all permutations with 1 in front
            function(keys, position+1, length, map)
            run(map)
    }

Create all combinations of mappings of characters to truth values

1 Answers1