java - 一个奇怪的计数器 - 无效的断开数字

Question

我想知道有没有办法这样算:

每个位置的基础:

4 2 3

计数器值:

000--invalid - exception, always a non zero digit must be there
001
002
010
011
012
100
101--invalid : disconnected digits
102--invalid : disconnected digits
110
111
112
200
201--invalid : disconnected digits
202--invalid : disconnected digits
210
211
212
300
301--invalid : disconnected digits
302--invalid : disconnected digits
310
311
312

这个想法是，如果非零数字由零分隔，则将这种形式排除在外。这意味着像 101、201 这样的值是无效的。

例如谈论十进制计数系统(最大值:9999)，不会产生像 1001 或 9010 这样的数字。

我想到了计数然后转换为每个基数，(在我的第一个例子中，基数是 4.2.3，对于 9999 的例子，它是 10.10.10.10)但是，所有数字中有一定数量它们将是有效的。

例如:

4.2.3: 17 out of 4*2*3 (or 24) will be valid
4.2.2.4: 30 out of 4*2*2*4 (or 64) will be valid
10.10.10.10: 8298 out of 10*10*10*10 (or 10000) will be valid.

随着位置的上升，我需要执行的计算也越多。

对于可以产生这样数字的快速计数器，您有什么想法？

我提到的一个简单的解决方案是计数和转换，然后对生成的数字进行后处理，但是优化的解决方案是什么？

这是我的代码:

/**
 * Author: Soleyman Pasban
 * Date: Apr 6, 2016 
 */
package PC;

public class DigitTest {

    public static void main(String[] test) {
        //int[] base = new int[]{4, 2, 3};
        int[] base = new int[]{4, 2, 2, 4};
        //int[] base = new int[]{10,10,10,10};

        int valid = 0;
        int total = 1;

        for (int i = 0; i < base.length; i++) {
            total *= base[i];
        }

        for (int i = 1; i < total; i++) {

            int number = i;
            int bi = base.length - 1;
            String str = "";
            while (bi >= 0) {
                str = number % base[bi] + str;
                number = number / base[bi];
                bi--;
            }

            boolean pass = true;
            boolean allowNonZero = true;

            for (int j = 1; j < base.length; j++) {
                if (str.charAt(j - 1) == '0' && str.charAt(j) != '0') {
                    //for the first case ...0* it should filter the cases
                    //I bypass it once by this, else the number must mark invalid
                    if (allowNonZero == false) {
                        pass = false;
                    }
                    allowNonZero = false;
                }
                //once see a zero, no none-zero must be appear
                if (str.charAt(j - 1) != '0') {
                    allowNonZero = false;
                }
            }

            if (pass) {
                valid++;
            } else {
                str += " - invalid";
            }

            System.out.println(str);

        }

        System.out.println();
        System.out.println("Valid: " + valid);
        System.out.println("Total: " + total);
    }
}

我的问题是是否有办法使上述算法保持简单。对于像 4.8.7.2.2.3.2.2.4.2.7.4.2.3.2.2 这样的 16 位数字(这是一个表明它必须与任何基数一起使用的示例)计算量，创建字符串变量和其他我认为会的东西效率低下!

例如，如果一个数字以 9010*********1 开头，那么这个数字从一开始就是错误的，计算其余部分将毫无意义。

这个问题还有其他解决办法吗？我想看看我是否可以通过这个生成有效数字。

谢谢

Answer 1

其实很简单。您首先创建一个 char[] 的 '0' 个适当长度的字符。

然后您递增最后一位数字，并在必要时翻转。更新后的数组就是下一个值，您可以使用 new String(buf) 创建结果。

现在，诀窍是当你翻转时，将数字设置回 0，然后向左移动一个位置，然后递增它。但是，您还记得在链式翻转期间必须向左移动多远，因为您必须在下一次迭代中递增最左边的零，以防止“数字断开”。

例子:

1999
2000  <-- rollover, remember that second digit must be incremented next
2100  <-- now remember that third digit must be incremented next
2110  <-- now remember that forth digit must be incremented next
2111  <-- normal increment
2112  <-- normal increment

由于像这样的怪异计数器如果可重用是最好的，这里是一个实现此逻辑的类，包括验证:

public final class WeirdCounter {
    private int[]  bases;
    private char[] buf;
    private int    idx;
    public WeirdCounter(int ... bases) {
        if (bases.length == 0)
            throw new IllegalArgumentException("No bases");
        for (int base : bases)
            if (base < 1 || base > 10)
                throw new IllegalArgumentException("Invalid base:" + base);
        this.bases = bases.clone();
        this.buf = new char[bases.length];
        Arrays.fill(this.buf, '0');
        this.idx = this.buf.length - 1;
    }
    public String next() {
        while (this.idx >= 0) {
            char digit = this.buf[this.idx];
            if (++digit < '0' + this.bases[this.idx]) {
                this.buf[this.idx] = digit;
                if (this.idx < this.buf.length - 1)
                    this.idx++;
                return new String(this.buf);
            }
            this.buf[this.idx--] = '0';
        }
        return null;
    }
}

这非常快速且易于使用:

WeirdCounter counter = new WeirdCounter(4,2,3);
for (String val; (val = counter.next()) != null; )
    System.out.println(val);

输出

001
002
010
011
012
100
110
111
112
200
210
211
212
300
310
311
312

请注意，您提供的 16 位示例 (4.8.7.2.1.3...4.6.7.9.10...3.1.1) 没有任何意义。 ... 是什么意思？此外，1 的基数意味着数字只能是 0。

因此，假设 . 表示 1，代码将起作用。当翻转超过任何此类以 1 为基数的值时，右侧的所有数字必须保持0。

使用 new WeirdCounter(4,8,7,2,1,3,1,4,6,7,9,10,1,3,1,1) 的部分输出:

...
0000000356870000
0000000356880000
0000000356890000
0000010000000000
0000020000000000
0001000000000000
0010000000000000
0011000000000000
0020000000000000
0021000000000000
0030000000000000
0031000000000000
0040000000000000
0041000000000000
0050000000000000
0051000000000000
0060000000000000
0061000000000000
0100000000000000
0110000000000000
0111000000000000
...

仍然，代码非常非常快，因为当它尝试递增 0001000000000000 时，它知道在 1 之后递增第一个零，所以它立即翻转base-1 数字，然后将 1 数字递增到 2，甚至不查看其他 0 数字。