3

所以我有一个清单：

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。如果数字没有重复，我只是将其添加到列表中。如果数字确实重复，我使用堆的算法来获得每个排列。

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

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

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

注 1：allLists 保存所有当前列表（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();
}
4

1 回答 1

1

假设：
我不知道您的输入格式，但我假设我有两个列表alphabets，其中包含字母values列表和对应值列表。两者长度相等，并且values按降序排列。

这是我解决问题的方法：

  1. 将输入转换为Map<Integer, List<String>> valuesToListMap = new TreeMap<>(Collections.reverseOrder());. 为什么？因为该映射将告诉我需要查找排列的子字符串（在您的示例中它会是{a},{b,c,d},{e,f},{g}，并且由于映射是类型TreeMap并且其中的条目将是反向自然排序（降序）顺序，我可以确保条目在地图按严格的降序排列。给定您的输入，我的地图中的示例条目将是18 -> {b,c,d}
  2. 接下来，我将遍历valuesToListMap. 我会找到每个列表的排列。对于我们的示例，输出将是{{a},{bcd,bdc,cbd,cdb,dbc,dcb},{ef,fe},{g}。让我们调用那个集合permutationsList
  3. 接下来，我将一次遍历permutationsList两个条目，并开始将第一个条目的每个元素附加到第二个条目的每个元素。例如，我会将 entry 的每个元素附加到 entry{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]

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

于 2017-09-21T18:12:18.877 回答