我想生成一个长字节数组,其中没有重复的大小为 N
的子序列。 N 很小,通常在 3 到 8 之间。
显然生成一个任意长的数组是不可行的:在大约 2^(8*N)
字节后,将有 2^(8*N)
子序列present 所以不会有任何唯一的留下来使用(因为有 2^(8*N) 个大小为 N
的唯一字节序列)。现在这是此类数组长度的上限,但不一定是下限)。我不需要可能的最长序列或类似的东西:例如,N == 4
的 1,000,000 个值可能就足够了,但至少应该可以检测到序列何时太长在某种生成策略下的唯一性。
理想情况下,生成策略很简单,就像在添加每个字节时检查每个先前的子序列一样。
我将 Java 放在具体位置,因为这是我目前正在使用它的地方,但这个概念确实适用于任何语言。
最佳答案
用户的关键观察harold in the comments , 是你可以创建一个最大序列而不用 de Bruijn sequence 重复元素N
的顺序。
这样的序列(它们不是唯一的)恰好包含所有可能的 N 元素子序列一次,因此将是一个没有 N 元素重复子序列的最大序列。
剩下的问题是,是否可以相当简单地生成此类序列的前缀,答案是肯定的。
按照本 blog post 中描述的方法进行操作可以生成所有 Lyndon Words大小为 N 或更小的数组,按字典顺序排列,并连接所有长度除以 N
的数组以创建我们想要的数组。
在 Java 中,字母表只是 256 字节的值,上述链接中的代码适用于处理固定长度的 byte[]
,如下所示:
/**
* Use an order-n de-Bruijn sequence to fill a byte array such that no n-length sub-array is repeated.
*/
public static void trucatedDeBruijnBytes(int n, byte[] arr) {
int written = generateLyndonBytes(1, 1, 256, new byte[n + 1], arr, 0);
if (written != arr.length) {
throw new RuntimeException("Can't generate a unique sequence of length " + arr.length + ", max is " + written);
}
}
private static int generateLyndonBytes(int t, int p, int k, byte[] a, byte[] output, int oidx) {
if (t == a.length) {
if((a.length-1)%p==0) {
int len = Math.min(p, output.length - oidx);
System.arraycopy(a, 1, output, oidx, len);
oidx += len;
}
} else {
a[t] = a[t-p];
assert a[t] < k;
if ((oidx = generateLyndonBytes(t+1,p, k, a, output, oidx)) == output.length) {
return oidx;
}
for(int j = (a[t-p] & 0xFF) + 1; j < k; j++) {
assert(j >= 0 && j < k);
a[t] = (byte)j;
assert a[t] < k;
if ((oidx = generateLyndonBytes(t+1,t, k, a, output, oidx)) == output.length) {
return oidx;
}
}
}
return oidx;
}
这可能可以进一步优化,但它已经相对有效:它只使用少量固定状态(byte[] a
数组,其大小为 N + 1
) 加上有限数量的递归(通常最多 N + 1
调用深度)和一些数学来“就地”生成所有值。比保留所有已见 N
序列的哈希值以执行重复数据删除的解决方案要好得多!
出于好奇,下面是 N == 2
序列的第一位:
[0, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 9, 0, 10, 0, 11, 0, 12, 0, 13, 0, 14, 0, ..., 125, 0, 126, 0, 127, 0, -128, 0, -127, ..., 0, -3, 0, -2, 0, -1, 1, 1, 2, 1, 3, 1, 4, 1, 5, ...]
所以 0
后跟一个简单的递增序列 0, i, 0, i + 1, ...
512 字节然后是序列 1, i , 1, i + 1, ...
等等。
关于java - 生成没有给定大小的重复子数组的长字节数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47209600/