0

我有一个包含以下数字的数组

int[] arr = {2,4,3,1,5,6,0,7,8,9,10,11,12,13,14,15};

或与此相关的任何其他命令。我需要使用递归对数字进行所有可能的组合，但要满足一个条件，即下一个与当前数字结合的数字只能来自哈希图给出的特定数字：例如，当递归取 1 时，下一个数字可以来自{0,4,5,2,6}（来自 HaspMap），然后如果我做 10，下一个数字可以来自 {1,4,5}等等

static HashMap<Integer,Integer[]> possibleSeq = new HashMap<Integer,Integer[] >();
private static void initialize(HashMap<Integer,Integer[]> possibleSeq) {
    possibleSeq.put(0,new Integer[]{1,4,5});
    possibleSeq.put(1,new Integer[]{0,4,5,2,6});
    possibleSeq.put(2,new Integer[]{1,3,5,6,7});
    possibleSeq.put(3,new Integer[]{2,6,7});
    possibleSeq.put(4,new Integer[]{0,1,5,8,9});
    possibleSeq.put(5,new Integer[]{0,1,2,4,6,8,9,10});
    possibleSeq.put(6,new Integer[]{1,2,3,5,7,9,10,11});
    possibleSeq.put(7,new Integer[]{2,3,6,10,11});
    possibleSeq.put(8,new Integer[]{9,4,5,12,13});
    possibleSeq.put(9,new Integer[]{10,4,5,8,6,12,13,14});
    possibleSeq.put(10,new Integer[]{7,6,5,9,11,15,13,14});
    possibleSeq.put(11,new Integer[]{6,7,10,14,15});
    possibleSeq.put(12,new Integer[]{8,9,13});
    possibleSeq.put(13,new Integer[]{8,9,10,12,14});
    possibleSeq.put(14,new Integer[]{9,10,11,13,15});
    possibleSeq.put(15,new Integer[]{10,11,14});    
}

注意：我需要从数字长度 1 到 10 开始所有可能的数字。救命！

4

1 回答 1

0

尝试这样的事情，对于初学者：

void findPath(Set paths, Stack path, int[] nextSteps, Set numbersLeft) {
    if (numbersLeft.isEmpty()) {
        //Done
        paths.add(new ArrayList(path));
        return;
    }

    for (int step:nextSteps) {
        if (numbersLeft.contains(step)) {
            // We can move on
            path.push(step);
            numbersLeft.remove(step);
            findPath(paths, path, possiblePaths.get(step), numbersLeft);
            numbersLeft.add(path.pop());
        }
    }       
}

起始值应该是一个空 Set 和一个空 Stack，一个与您的初始数组相同的 nextSteps，以及一个从您的初始数组创建的集合。当它返回时，应该用可能的路径填充路径集。

我没有对此进行测试，并且存在错误以及更优雅的解决方案。

于 2013-08-08T07:40:06.327 回答