java - 一个奇怪的计数器 - 无效的断开数字
java - a weird counter - invalid disconnected digits
想知道有没有这样算的方法：
每个位置的基数：
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.
位置越高，我需要执行的计算就越多。
对于可以产生这样数字的快速计数器，您有什么想法？
我提到的一个简单的解决方案是计算和转换，然后对生成的数字进行 post 处理，但是优化的解决方案是什么？
这是我的代码：
/**
* 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 开头，那么这个数字从一开始就是错误的，计算其余部分将毫无意义。
这个问题还有其他解决办法吗？我想看看我是否可以通过这个产生有效数字。
谢谢
这是一种不会生成任何无效数字的超快速方法。只需为不同的碱基序列更改 maxdigits 和 current 的初始值设定项即可。
它的工作原理是直接递增前一个数字，所以如果你愿意，你可以用它做一个迭代器。
这是一个很好的模式，需要记住才能按词汇顺序生成各种不同类型的序列：
鉴于 "current item"，您始终可以通过以下 2 个步骤制作下一个项目：
- 递增最右边可以大于当前项中对应字符的字符。这是有效的，因为下一个项目必须更大，并且必须与当前项目共享最长的可能前缀。然后
- 将剩余的字符设置为尽可能低的值，否则您会跳过一些字符。
这些步骤可以很容易地生成你的序列，实际上还有很多其他按词汇顺序排列的序列。
public static void main (String[] args) throws java.lang.Exception
{
char[] maxdigits = "312".toCharArray();
char[] current = "001".toCharArray();
for (;;)
{
System.out.println(new String(current));
//each time we add 1, one digit is incremented by one,
//and all the lower-place digits are set to the least possible
//value
//Step 1 - find the position of digit to increment
boolean sawNonZero=false;
int incpos;
for(incpos = current.length-1; incpos>=0; --incpos)
{
if (current[incpos]=='0')
{
if (sawNonZero || current[incpos-1]!='0')
{
//can increment a leading zero or the first trailing zero
break;
}
//incrementing this one would create a zero gap
}
else
{
sawNonZero = true;
if (current[incpos]<maxdigits[incpos])
{
//can increment a digit that is less than max
break;
}
}
}
if (incpos<0)
{
break; //done
}
current[incpos]++;
//Step 2 - set the remaining digits to 0
for (incpos+=1; incpos<current.length; ++incpos)
{
current[incpos]='0';
}
}
}
public class Digits {
// make constructor or something
int[] base = new int[]{4, 2, 3};
int[] cur = new int[]{0, 0, 0};
public void find(int i, boolean hasNonZero) {
if (i == base.length) {
if (!hasNonZero) {
return; // all zeroes corner case
}
// output
for (int j = 0; j < base.length; j++) {
System.out.print(cur[j]);
}
System.out.println();
return;
}
for (int v = 0; v < base[i]; v++) { // each digit at position
if (hasNonZero && v != 0 && cur[i - 1] == 0) { // disconnected non zeroes
continue;
}
cur[i] = v;
find(i + 1, hasNonZero || v != 0); // next position
}
}
public static void main(String[] args) {
(new Digits()).find(0, false);
}
}
像这样的简单递归。
您可以在不生成任何数字的情况下计算计数。这里有一个简单的 O(n^3) 解决方案来演示这个想法。它可能可以进一步改进。
public class DigitTest {
public static void main(String[] args) {
countWeirdNumbers(4, 2, 3);
countWeirdNumbers(4, 2, 2, 4);
countWeirdNumbers(10, 10, 10, 10);
}
public static void countWeirdNumbers(int... bases) {
long count = 0;
for (int start = 0; start < bases.length; start++) {
for (int end = start; end < bases.length; end++) {
int thisCount = 1;
for (int i = start; i <= end; i++) {
thisCount *= bases[i] - 1;
}
count += thisCount;
}
}
System.out.println(count);
}
}
我们的想法是，您只是计算有多少数字在第一个和最后一个非零数字之间没有任何零。因此，遍历这两个数字的所有可能位置，并计算该范围内数字的可能性。每个数字都有 b-1 种可能性，其中 b 是该位置的基数，因为 0 是不允许的。
其实很简单。您首先创建一个 char[] 个 '0' 个字符的适当长度。
然后您递增最后一位数字，并在必要时翻转。更新后的数组就是下一个值，您可以使用 new String(buf).
创建结果
现在，诀窍是当你翻转时，将数字设置回 0，然后向左移动一个位置，然后递增。但是，您还记得在链式翻转期间必须向左移动多远，因为您必须在下一次迭代中递增最左边的零，以防止 "disconnected digits".
示例：
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
因为像这样的怪异计数器如果可重复使用是最好的，这里是 class 实现这个逻辑，包括验证：
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 数字。
想知道有没有这样算的方法：
每个位置的基数：
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.
位置越高，我需要执行的计算就越多。
对于可以产生这样数字的快速计数器，您有什么想法？
我提到的一个简单的解决方案是计算和转换，然后对生成的数字进行 post 处理，但是优化的解决方案是什么？
这是我的代码：
/**
* 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 开头，那么这个数字从一开始就是错误的，计算其余部分将毫无意义。
这个问题还有其他解决办法吗？我想看看我是否可以通过这个产生有效数字。
谢谢
这是一种不会生成任何无效数字的超快速方法。只需为不同的碱基序列更改 maxdigits 和 current 的初始值设定项即可。
它的工作原理是直接递增前一个数字，所以如果你愿意，你可以用它做一个迭代器。
这是一个很好的模式，需要记住才能按词汇顺序生成各种不同类型的序列：
鉴于 "current item"，您始终可以通过以下 2 个步骤制作下一个项目：
- 递增最右边可以大于当前项中对应字符的字符。这是有效的，因为下一个项目必须更大，并且必须与当前项目共享最长的可能前缀。然后
- 将剩余的字符设置为尽可能低的值，否则您会跳过一些字符。
这些步骤可以很容易地生成你的序列，实际上还有很多其他按词汇顺序排列的序列。
public static void main (String[] args) throws java.lang.Exception
{
char[] maxdigits = "312".toCharArray();
char[] current = "001".toCharArray();
for (;;)
{
System.out.println(new String(current));
//each time we add 1, one digit is incremented by one,
//and all the lower-place digits are set to the least possible
//value
//Step 1 - find the position of digit to increment
boolean sawNonZero=false;
int incpos;
for(incpos = current.length-1; incpos>=0; --incpos)
{
if (current[incpos]=='0')
{
if (sawNonZero || current[incpos-1]!='0')
{
//can increment a leading zero or the first trailing zero
break;
}
//incrementing this one would create a zero gap
}
else
{
sawNonZero = true;
if (current[incpos]<maxdigits[incpos])
{
//can increment a digit that is less than max
break;
}
}
}
if (incpos<0)
{
break; //done
}
current[incpos]++;
//Step 2 - set the remaining digits to 0
for (incpos+=1; incpos<current.length; ++incpos)
{
current[incpos]='0';
}
}
}
public class Digits {
// make constructor or something
int[] base = new int[]{4, 2, 3};
int[] cur = new int[]{0, 0, 0};
public void find(int i, boolean hasNonZero) {
if (i == base.length) {
if (!hasNonZero) {
return; // all zeroes corner case
}
// output
for (int j = 0; j < base.length; j++) {
System.out.print(cur[j]);
}
System.out.println();
return;
}
for (int v = 0; v < base[i]; v++) { // each digit at position
if (hasNonZero && v != 0 && cur[i - 1] == 0) { // disconnected non zeroes
continue;
}
cur[i] = v;
find(i + 1, hasNonZero || v != 0); // next position
}
}
public static void main(String[] args) {
(new Digits()).find(0, false);
}
}
像这样的简单递归。
您可以在不生成任何数字的情况下计算计数。这里有一个简单的 O(n^3) 解决方案来演示这个想法。它可能可以进一步改进。
public class DigitTest {
public static void main(String[] args) {
countWeirdNumbers(4, 2, 3);
countWeirdNumbers(4, 2, 2, 4);
countWeirdNumbers(10, 10, 10, 10);
}
public static void countWeirdNumbers(int... bases) {
long count = 0;
for (int start = 0; start < bases.length; start++) {
for (int end = start; end < bases.length; end++) {
int thisCount = 1;
for (int i = start; i <= end; i++) {
thisCount *= bases[i] - 1;
}
count += thisCount;
}
}
System.out.println(count);
}
}
我们的想法是，您只是计算有多少数字在第一个和最后一个非零数字之间没有任何零。因此，遍历这两个数字的所有可能位置，并计算该范围内数字的可能性。每个数字都有 b-1 种可能性，其中 b 是该位置的基数，因为 0 是不允许的。
其实很简单。您首先创建一个 char[] 个 '0' 个字符的适当长度。
然后您递增最后一位数字，并在必要时翻转。更新后的数组就是下一个值，您可以使用 new String(buf).
现在，诀窍是当你翻转时，将数字设置回 0，然后向左移动一个位置，然后递增。但是，您还记得在链式翻转期间必须向左移动多远，因为您必须在下一次迭代中递增最左边的零，以防止 "disconnected digits".
示例：
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
因为像这样的怪异计数器如果可重复使用是最好的，这里是 class 实现这个逻辑，包括验证：
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 数字。