java - 为列表的一个子部分内的排列创建数组

Question

所以我有一个列表:

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

对于每个匹配的数字，我必须获取标识符的每个排列。我需要的示例列表如下:

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

我目前正在采取的解决问题的步骤:

1. 读取列表，将每个值放入一个数组 ([a][12]) 并将其放入 ArrayList
2. 然后我找出是否有任何重复的数字并在 HashMap 中记下它
3. 然后我设置了一个 for 循环来遍历 HashMap。如果号码没有重复，我就把它添加到列表中。如果数字确实重复，我会使用 Heap 的算法来获得每个排列。

如果我要完成它，我会将数字添加到这样的列表中:

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

我当前的代码无法按预期工作(仅生成一个列表)，我什至不确定如何开始编写能够不断生成新列表并附加旧列表的代码。很抱歉迷路了，我现在正在上数据结构类(class)，感觉不在我的熟悉范围内(我们刚刚开始讨论链表)。

注1:allLists保存所有当前列表(a,abcd,adcb,)，permutationList保存列表的所有排列。

注意 2:我通过一个 boolean 列表来做这件事，但使用字母作为我想要完成的事情的简单视觉表示

我预计问题所在的代码:

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();
}

Answer 1

假设:
我不知道您的输入格式，但我假设我有两个列表 alphabets其中有字母列表和values其中有对应值的列表。两者长度相等且 values递减顺序。

这是我解决问题的方法:

1. 将输入转换为 Map<Integer, List<String>> valuesToListMap = new TreeMap<>(Collections.reverseOrder()); .为什么？因为该映射将告诉我需要为其查找排列的子字符串(在您的示例中它将是 {a},{b,c,d},{e,f},{g} 并且由于映射的类型为 TreeMap 并且其中的条目将以反向自然排序(降序)顺序排列，我可以确保 map 中的条目严格按降序排列。根据您的输入，我的 map 中的示例条目将为 18 -> {b,c,d}
2. 接下来，我将遍历 valuesToListMap 的值.我会找到每个列表的排列。对于我们的示例，输出将是 {{a},{bcd,bdc,cbd,cdb,dbc,dcb},{ef,fe},{g} .我们称该集合为 permutationsList
3. 接下来，我将遍历 permutationsList一次两个条目，并开始将第一个条目的每个元素附加到第二个条目的每个元素。例如，我将附加条目的每个元素 {a}在 permutationsList与条目的每个元素 {bcd,bdc,cbd,cdb,dbc,dcb} .所以合并后我的输出将是 {abcd,abdc,acbd,acdb,adbc,adcb}
4. 继续递归执行第 3 步，您应该得到输出

一些注意事项:
使用 TreeMap确保我们没有输出 bcdaefg因为这不是按值的降序排列。

我的解决方案如下。我没有进行任何输入验证或健全性检查，但这应该很容易做到:

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);
}

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

希望我的解释很清楚。如果您有任何问题，请告诉我。