java - 序列生成/广度优先搜索

Question

本质上，我正在做的是尝试通过广度优先搜索所有可能的 Action 来解开魔方。我知道这不是解决多维数据集的最佳方法，但我只需要它来处理非常短的序列(因此搜索深度不太可能超过 3)，而且除了当前序列。

我正在尝试找到一种打印出不断增加的数字字符串 (0,1,2,00,01,02...) 的方法，这样我就可以将每个数字插入一个函数来检查是否特定的移动顺序解决了立方体，但我无法找到无限期地继续该序列的方法。

到目前为止，我所管理的都是嵌套的 for 循环，但每次搜索变得更深入时都需要另一个循环。有谁知道我该如何解决这个问题？

抱歉，如果我说得太含糊了，我可以写一篇关于我正在尝试做的事情的文章，但我想我会尽量保持简单。

Answer 1

我对 Java 库中的内容不是很熟悉，如果这是实现已经存在的东西，我深表歉意，但如果我从头开始编写，我可能会这样做:

public class Enumerator {
    private int maxDepth;
    private int currentDepth;
    private int currentPerm;
    private String alphabet;

    public Enumerator(String alphabet, int d) {
        this.maxDepth = d;
        this.currentDepth = 1;
        this.currentPerm = 0;
        this.alphabet = alphabet;
    }

    public boolean next() {
        int numPermutations = (int) Math.pow(alphabet.length(), this.currentDepth);
        boolean res=false;

        // finished if
        if ((this.currentDepth == this.maxDepth) && 
            (this.currentPerm == numPermutations - 1)) {
            res = false;
        }
        // next perm at this depth
        else if (this.currentPerm < numPermutations - 1) {
            this.currentPerm++;
            res = true;
        }
        // next depth
        else if (this.currentDepth <= this.maxDepth) {
            this.currentDepth++;
            this.currentPerm = 0;
            res = true;
        }
        return res;
    }

    public String getPermutation() {
        int tmpPerm = this.currentPerm;
        String res = "";
        for (int i=0; i<this.currentDepth; i++) {
          int ind = tmpPerm % this.alphabet.length();
          res = this.alphabet.charAt(ind) + res;
          tmpPerm /= this.alphabet.length();
        }
        return res;
    }

    public static void main(String args[]) {
        int depth = 3;
        String alphabet = "012";
        Enumerator e = new Enumerator(alphabet, depth); 
        do {
            System.out.println(e.getPermutation());
        } while (e.next());
    }
}

这样你就可以枚举从任意符号的字母表到任意深度的序列。只要它遍历深度并且为每个深度生成完整的可能序列集，这也可以满足您的需求。正如 Gian 所说，它也可以通过递归来完成，这可能更优雅。在 Python 中，我会为此使用生成器函数，但我对 Java 中的任何类似内容都不熟悉。