javaarraysarraylistpermutationheaps-algorithm

Creating arrays for permutations within a subsection of a list

So I have a list:

a 25
b 18
c 18
d 18
e 14
f 14
g 12
... and so on

For each number that matches, I have to get every permutation of the identifier. The lists I would need from my example would be as follows:

abcdefg
abdcefg
acbdefg
acdbefg
adbcefg
adcbefg
abcdfeg
abdcfeg
acbdfeg
acdbfeg
adbcfeg
adcbfeg

Steps I am taking currently to solve the problem:

  1. Read in the list, place each value in an array ([a][12]) and place that in an ArrayList
  2. I then find if there are any repeating numbers and make note of it within a HashMap
  3. I then have a for loop set up to go through the HashMap. If the number didn't repeat, I just add it to the list. If the number did repeat, I use Heap's algorithm to get every permutation.

If I were to work through it, I would be adding the numbers to a list like this:

a
abcd
abdc
adbc
...
abcdef
abcdfe
abdcef
adbcfe
...
abcdefg
abcdfeg

My current code doesn't work as intended (generates only one list) and I'm not even sure how to begin writing a code that would continuously generate new lists, while also appending the old lists. I apologize for being lost, I'm in a data structures course right now and it all feels out of my familiarity zone (we just started discussing linked lists).

Note 1: allLists holds all the current lists (a, abcd, adcb,) and permutationList holds all the permutations of the list.

Note 2: I'm doing this through a boolean list, but used letters as an easy visual representation for what I'm trying to accomplish

Code where I expect the problem to be:

public static Boolean[] combine (int i, int j) {
    int aLen = allLists.get(j).length;
    int bLen = permutationList.get(i).length;

    Boolean[] newList = new Boolean[aLen + bLen];
    System.arraycopy(allLists.get(j), 0, newList, 0, aLen);
    System.arraycopy(permutationList.get(i), 0, newList, aLen, bLen);

    return newList;
}

public static void setAllLists() {
    if(allLists.size() == 0) {
        allLists.add(permutationList.get(0));
    }

    for(int i = 0; i < permutationList.size(); i++) {
            for(int j = 0; j < allLists.size(); j++) {
                Boolean[] newList = combine(i,j);
                if(i == 0) {
                    allLists.set(j, newList);
                }
                else {
                    allLists.add(newList);
            }
        }
    }
    permutationList.clear();
}
Solution

  • Assumptions:
    I don't know your input format but I have assumed that I have two lists alphabets which have list of alphabets and values which have list of corresponding values. Both are equal in length and values are in decreasing order.

    Here's my approach to the problem:

    1. Convert the input to a Map<Integer, List<String>> valuesToListMap = new TreeMap<>(Collections.reverseOrder());. Why? Because that map will tell the substrings I would need to find permutations for (in your example it would be {a},{b,c,d},{e,f},{g} and since the map is of type TreeMap and the entries in it will be in reverse natural ordering (descending) order, I can ensure the entries in the map are in strictly decreasing order. Sample entry in my map given your input will be 18 -> {b,c,d}
    2. Next, I will iterate through the values of the valuesToListMap. I will find permutations of every list. For our example the output would be {{a},{bcd,bdc,cbd,cdb,dbc,dcb},{ef,fe},{g}. Lets call that collection permutationsList
    3. Next, I will iterate over the permutationsList two entries at a time and start appending each element of first entry with each element of second entry . For example, I will append each element of entry {a} in permutationsList with each element of entry {bcd,bdc,cbd,cdb,dbc,dcb}. So my output after the merge will be {abcd,abdc,acbd,acdb,adbc,adcb}
    4. Continue doing step 3 recursively and you should have your output

    Some notes:
    Using TreeMap ensures we don't have an output bcdaefg because that is not in descending order of values.

    My solution is below. I have not done any input validation or sanity checks but that should be easy to do:

    public class PermutationWithinSubsection {
public static void main(String[] args) {
    List<String> alphabets = Arrays.asList("a","b","c","d","e","f","g");
    List<Integer> values = Arrays.asList(25,18,18,18,14,14,12);
    // Step 1 start
    Map<Integer, List<String>> valuesToListMap = new TreeMap<>(Collections.reverseOrder()); // Order the map in reverse order of values
    for(int i=0; i<alphabets.size(); i++) {
        if(valuesToListMap.containsKey(values.get(i))) {
            List<String> temp = valuesToListMap.get(values.get(i));
            temp.add(alphabets.get(i));
            valuesToListMap.put(values.get(i),temp);
        } else {
            List<String> temp = new ArrayList<>();
            temp.add(alphabets.get(i));
            valuesToListMap.put(values.get(i), temp);
        }
    }
    // Step 1 end

    // Step 2 start
    List<List<String>> permutationsList = new ArrayList<>();
    for(List<String> ip: valuesToListMap.values()) {
       List<String> result = new PermutationWithinSubsection().permute(ip);
        permutationsList.add(result);
    }
    // Step 2 end

    // // Step 3 start
    int count = 1;
    List<String> l1 = permutationsList.get(0);
    List<String> r = new PermutationWithinSubsection().merge(l1, permutationsList, count);
    // // Step 3 end
    System.out.println("r = " + r);
}

/**
 * Find permutations of input list using backtracking
 * @param ip
 * @return
 */
private List<String> permute(List<String> ip) {
    List<String> list = new ArrayList<>();
    backtrack(list, new ArrayList<>(), ip);
    return list;
}

private void backtrack(List<String> list, ArrayList<String> tempList, List<String> nums) {
    if(tempList.size() == nums.size()){
        StringBuilder sb = new StringBuilder();
        for(String s: tempList) {
            sb.append(s);
        }
        list.add(sb.toString());
    } else{
        for(int i = 0; i < nums.size(); i++){
            if(tempList.contains(nums.get(i))) continue; // element already exists, skip
            tempList.add(nums.get(i));
            backtrack(list, tempList, nums);
            tempList.remove(tempList.size() - 1);
        }
    }
}


/**
 * Keep on merging lists till we have merged all
 * @param l1
 * @param resultLists
 * @param count
 * @return
 */
private List<String> merge(List<String> l1, List<List<String>> resultLists, int count) {
    if(count == resultLists.size()) {
        return l1;
    }
    List<String> l2 = resultLists.get(count);
    List<String> f = new ArrayList<>();
    for(String s1: l1) {
        for(String s2: l2) {
            f.add(s1+s2);
        }
    }
    return merge(f,resultLists,++count);
}

    }

    Output: r = [abcdefg, abcdfeg, abdcefg, abdcfeg, acbdefg, acbdfeg, acdbefg, acdbfeg, adbcefg, adbcfeg, adcbefg, adcbfeg]

    Hope my explanation was clear. Let me know if you have any questions.