在 6^26 字符串数组中查找长度为 6 的字符串 [已关闭]

Question

我有一个任务是创建一个 JS 脚本，该脚本能够在包含长度为 6 的字母字符（仅小写）的所有排列的数组上使用二分搜索来查找字符串 - 意味着这种形式的所有字符串：

['aaaaaa','aaaaab','aaaaac'.... 'zzzzzx','zzzzzy','zzzzzz']

（数组中总共 26^6 个项目）

由于其大小 - 我无法在本地生成数组并对其运行常规二分搜索，我需要能够在 n/2 位置 (n = 26^6) 中找到字符串而不创建数组。

另一方面 - 我需要在任何字符串（'aaaaaa'，'zzzzzz'）到数字之间创建某种一对一的映射，然后我可以创建相反的方式（从数字到字符串）进行除法计算并找到中间的字符串等等。

最好是用 JS/TS 编写，因为我最终想用它制作一个节点应用程序。

有什么想法吗？

Answer 1

你可以做一些像二进制数一样的事情，我的意思是用base26写下数字，然后使用指数在相应的位置找到相应的字母。

let number = (26**6)/2
let exponants = number.toString(26)
let correspondingString = exponants
  .split('')
  .map(elem => parseInt(elem, 26))
  .map(elem => (elem + 10).toString(36))
  .join('')
console.log(correspondingString);

然后反过来：

let string = 'naaaaa'
let correspondingNumber = string
  .split('')
  .map(elem => parseInt(elem, 36) - 10)
  .map((elem, index) => elem*(26**(5-index)))
  .reduce((sum, value)=> sum + value, 0)
console.log(correspondingNumber);
console.log(correspondingNumber == (26**6)/2)

Answer 2

注意

这个解决方案在某种程度上将问题推广到更大的数字。与问题相关的数字仍然可以通过标准 JS 数字类型来容纳。

解决方案

您可以使用 JS 的

BigInt 对象

（任意大小的整数）找到给定数字的 a-z 表示形式。

如果您要在排序器排列列表中查找第

n/2

号，您可以按以下步骤操作：

let bn_x  = ((26n ** 6n) / 2n)  // BigInt notation
  , s_x26 = bn_x.toString(26)   // Convert in base 26. Digits are represented by 0-9,a-q
  , s_atoz                      // Will hold s_x26 with digits represented by a-z
  ;

  s_atoz =
  Array
     .from(s_x26)    // string -> array of chars (ie. array of single-letter strings)
     .map ( c => {   // map a-q -> k-z, 0-9 -> a-j
         return String.fromCharCode((( c.charCodeAt(0) < 'a'.charCodeAt(0) ) ? (c.charCodeAt(0) + ( 'a'.charCodeAt(0) - '0'.charCodeAt(0) )) : ( c.charCodeAt(0) + 10 )));
      })
     .join('')       // array of chars -> string
  ;

  console.log(s_atoz);

当然，这个具体结果也可以不经过计算而推导出来。

相反的工作方式与基本思想类似，但有一个警告：在撰写本文时，没有基数感知的 BigInt 构造函数，因此需要使用基数构造的基本步骤来组装数字。

let s_atoz = 'naaaaa'
  , abn_x26  = 
  Array
     .from(s_atoz)
     .map ( c => {
         return BigInt(c.charCodeAt(0) - 'a'.charCodeAt(0));
      })
  , bn_x = abn_x26.reduce ( (previousValue, currentValue) => {
               return BigInt(previousValue) * 26n + BigInt(currentValue);
           }
         , 0n
       )
  ;

  console.log(bn_x.toString());

Answer 3

如果您只想找到在我们的假想数组中给定位置出现的字符串，我们可以使用这个

numberToString

函数来计算它：

const n2s = (chars, len = chars .length) => (n) => 
  (n < len ? '' : n2s (chars, len) (~~ (n / len))) 
  + chars [n % len] 

const fixedN2s = (digits, chars) => (n) =>
  n2s (chars) (n) .padStart (digits, chars [0])

const numberToString = fixedN2s (6, 'abcdefghijklmnopqrstuvwxyz')


; [28, 268041553, 202214284, 26 ** 6 / 2] .forEach (
  s => console .log (`numberToString (${s}) //=> "${numberToString (s)}"`)
)

我们从一个辅助函数开始，它完成大部分工作，首先接受我们想要使用的字母表。 这里都是小写字母，但我们可以很容易地想象对“abcde”做同样的事情。 它返回一个接受数字的函数，然后我们剥离该数字的最后一个“数字：”，使用它作为最后一个字符的

chars

的索引，然后对于字符串的其余部分返回一个空字符串（在我们的基本情况下，当

n

小于我们的字符数时）或递归调用的值，该数字被剥离，剩余的数字通过将我们的字符数除以余数来转移。

我们对函数

fixedN2s

进行分层，该函数使用附加的

digits

参数来调用上面的函数，该参数告诉要预填充第一个字符的固定位置的数量。 也就是说，

n2s ('abc...z') (28)

会产生

'bc'

，但我们想用

a

预填充，以获得

'aaaabc'

。

我们使用传递

6

和我们的字母表到此函数来创建

numberToString

，我们的主要函数。

---

请注意，我们也可以简单地进行相反的操作，例如以下代码片段：

const s2n = (chars,
   encoding = [...chars] .reduce ((a, d, i) => ((a [d] = i), a), {})
) => ([...ss]) => ss .length == 0 
  ? 0 
  : chars .length * s2n (chars, encoding) (ss .slice (0, -1)) + encoding [ss .at (-1)]

const stringToNumber = s2n ('abcdefghijklmnopqrstuvwxyz')


; ['abc', 'woolen', 'random', 'naaaaa'] .forEach (
  s => console .log (`stringToNumber ("${s}") //=> ${stringToNumber (s)}`)
)