发单-伪随机序列函数

[kuber]

通过算法生成一串二进制数列，总长度大于等于65536。

对于 x(x=1 ，2 ，3 ，4 ，5 ，6………n)，n 最大为 65536 ，f(x)等于 1 个 32 位二进制数; f(x+1)为 f(x)的值在这个序列里面后移一位，f(x+2)为 f(x)的值在这个序列里面后移两位, 以此类推。并满足以下条件：

1. x 为连续的，每个 f(x)对应的 32 位二进制数一一对应，没有重复;
2. 每个 f(x)对应的 32 位二进制数中，0 和 1 的个数差值不超过 4
3. 整个 65536 长序列中需要有一段序列，其中连续 0 和 1 的个数<=8 位;

交付物：

1. 序列生成函数以及相应的 unit tests 。语言没有什么要求，是常见的编程语言的就可以，如python, java, c# 等等，但是最好不要使用商业付费软件/包如 MATLAB~~~
2. 提供如何计算的数学公式 f(x)

有兴趣的同学请留下编码的邮箱。最好以前有写过类似功能的经验。AIGC 也不太能处理，我尝试过几个模型，写出来的都不对。对需求有什么疑问也可以在下面留言，我会尽快回复。

合作的话，谈好价钱之后会要求先写 unit tests ，确认对需求的理解一致后付第一笔钱，然后再写实现代码。

这一句条件有笔误 “整个 65536 长序列中需要有一段序列，其中连续 0 和 1 的个数<=8 位;”。 应该是“整个 65536 长序列中需要每一段序列，其中连续 0 和 1 的个数<=8 位;”

另外有一个点我没有写清楚，需要提供f(x) 函数，而不是暴力的方式随机产生一个数然后验证是否符合条件。 需要给定一个32 位的序列，反向算出x，并且时间小于20ms。

[lanjun]

有点意思，插个眼，明天上班写一写，[email protected]

[kalinzhang]

lz 看看这个是不是一个符合要求的串 https://pastebin.pl/view/d8bc2c6f
单元测试也可以提供
我的邮箱是 a2FyaW56aGFuZzIzIEFUIGdtYWlsLmNvbQ==

[HDY]

是我理解错了吗，第三条的条件是不是有问题

[boomboom5432]

密码里这种需求不常见，这种功能写一星期半个月都可能，先报预算才会有人去研究

[tlxxzj]

不知我理解得对不对， 看代码：

https://leetcode.cn/playground/7iu298LX/

[tlxxzj]

import sys
import os


class Solution:
def generate_bits(self, n: int = 65536) -> tuple[bool, list[int]]:
"""Generate n bits with the following constraints:
1. the diff between the number of 0s and 1s in each 32-bit number is at most 4
2. each 32-bit number is unique
3. no more than 8 consecutive 0s or 1s
Args:
n: the number of bits to generate, n >= 65536
Returns:
A tuple of two elements:
- True if the bits are successfully generated, False otherwise
- A list of n bits if the bits are successfully generated, an empty list otherwise
"""

# increase the recursion limit
sys.setrecursionlimit(max(sys.getrecursionlimit(), n * 2))

visited_nums = set() # set to store visited numbers
bits = [] # list to store generated bits

def dfs(i, c0, c1, diff, num: int) -> bool:
"""
Depth-first search to generate bits recursively
Args:
i: the index of the current bit
c0: the number of 0s in the current 32-bit number
c1: the number of 1s in the current 32-bit number
diff: the diff between the number of 0s and 1s
num: the current 32-bit number
Returns:
True if the bits are successfully generated,
False otherwise
"""

# verify the diff between the number of 0s and 1s in each 32-bit number is at most 4
if c0 - c1 > 4 or c1 - c0 > 4 or diff > 4 or diff < -4:
return False

# return True if all bits are generated
if i == n:
return True

# first 32 bits
if i < 32:
next_num = num * 2
# the rest bits
else:
next_num = (num & 0x7fffffff) * 2
# remove the leftmost bit
if bits[i - 32] == 0:
c0 -= 1
else:
c1 -= 1

x = self.random_bit() # randomly choose 0 or 1

# if x == 0, try 0 first
if x == 0 and (next_num not in visited_nums):
visited_nums.add(next_num)
bits.append(0)
if dfs(i + 1, c0 + 1, c1, diff - 1, next_num):
return True
visited_nums.remove(next_num)
bits.pop()

# if x == 0, fallback to 1
# if x == 1, try 1
next_num += 1
if next_num not in visited_nums:
visited_nums.add(next_num)
bits.append(1)
if dfs(i + 1, c0, c1 + 1, diff + 1, next_num):
return True
visited_nums.remove(next_num)
bits.pop()

# if x == 1, fallback to 0
next_num -= 1
if x == 1 and (next_num not in visited_nums):
visited_nums.add(next_num)
bits.append(0)
if dfs(i + 1, c0 + 1, c1, diff - 1, next_num):
return True
visited_nums.remove(next_num)
bits.pop()

return False

found = dfs(0, 0, 0, 0, 0)
if found and self.verify_bits(bits):
return True, bits
return False, bits

def random_bit(self) -> int:
"""Generate a random bit
"""
return os.urandom(1)[0] & 1

def verify_bits(self, bits: list[int]) -> bool:
"""Verify the generated bits
"""

n = len(bits)

# verify: the diff between the number of 0s and 1s in each 32-bit number is at most 4
for i in range(32, n+1):
c1 = sum(bits[i - 32:i])
c0 = 32 - c1
if c0 - c1 > 4 or c1 - c0 > 4:
print("Failed at diff constraint!")
return False

# verify: each 32-bit number is unique
visited_nums = set()
for i in range(32, n+1):
num = 0
for j in range(i-32, i):
num = num * 2 + bits[j]
if num in visited_nums:
print("Failed at unique constraint!")
return False
visited_nums.add(num)

# verify: no more than 8 consecutive 0s or 1s
c0, c1 = 0, 0
for i in range(n):
if bits[i] == 0:
c0 += 1
c1 = 0
else:
c1 += 1
c0 = 0
if c0 > 8 or c1 > 8:
print("Failed at consecutive constraint!")
return False

return True



if __name__ == "__main__":
sol = Solution()
n = 65536
found, bits = sol.generate_bits(n)
if found:
print("Bits are successfully generated!")
#print(bits)
else:
print("Failed to generate bits!")

[kuber]

@HDY 谢谢指出。的确是笔误。

[kuber]

@boomboom5432 嗯嗯，是的。这就是一个 m 序列问题。对于没有做过的人，从头学习是挺难的。但是做过的人就很快。

[kuber]

@kalinzhang @tlxxzj 我补充了一点说明，之前可能写的不够明确。需要提供计算的 f(x), 这样能反向推算出 x

[kalinzhang]

@kuber 预算是多少？我大概可以推一推，但需要看预算决定要不要花时间推导

[kuber]

@kalinzhang 能留个联系方式吗，邮箱或者微信