在列表的子区域内创建排列数组

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

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

< li >读入列表，将每个值放入一个数组([a][12])，然后将它放入一个ArrayList中 < li >然后我会查找是否有重复的数字，并在散列表中记录下来 < li >然后我设置了一个for循环来遍历HashMap。如果号码没有重复，我就把它加到名单上。如果数字重复，我使用堆的算法得到每一个排列。

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

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

我当前的代码没有按预期工作（只生成一个列表），我甚至不确定如何开始编写一个代码来不断生成新列表，同时还要附加旧列表。我很抱歉迷路了，我现在在数据结构课程中，这一切都超出了我的熟悉范围（我们刚刚开始讨论链接列表）。

注1：allList保存所有当前列表（a、abcd、adcb、），而perMutationList保存列表的所有排列。

注2:我通过一个布尔列表来做这件事，但是使用字母作为我试图完成的事情的一个简单的可视化表示

我期望问题出现的代码：

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

假设：我不知道
你的输入格式，但我假设我有两个列表字母表，它们有字母表列表和值列表，它们有相应的值列表。两者的长度相等，值按降序排列。

以下是我解决这个问题的方法:

< li >将输入转换为< code >映射

一些注意事项：
使用树状图可以确保我们没有输出 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);
}

}

输出：＜code＞r=[abcdefg、abcdfeg、ABDCFG、abdcfeg、ACBDFG、acbdfeg、acdbefg、acdbfeg、adbcefg、ADBC FEG、adcbefg、adcbfeg]

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