一串整数拼图

Question

我为没有数学背景以更正式的方式提出这个问题而道歉.我正在寻找创建一个具有特定属性的796个字母(或整数)的字符串.

基本上,该字符串是De Bruijn序列B(12,4)的变体,除了忽略每个n长度子序列内的顺序和重复.即ABBB BABA BBBA各自相当于{AB}.换句话说,字符串的主要属性包括查看较大字符串中的4个字母的连续组(即第1到第4个字母,第2到第5个字母,第3个到第6个字母等)然后生成一组包含每个组的字母(重复和顺序被忽略)

例如,在9个字母的字符串中:

ABBACEBCD

第一个4个字母的组是:ABBA,它由集合{AB}组成,第二个组是:BBAC,它由集合{ABC}组成,第三个组是:BACE,它由集合{ABCE组成等等

目标是来自一组N个字母的1-4个字母的每个组合由4个元素组的1-4个字母的结果集合表示,并且在原始字符串中仅一次.

例如,如果有一组5个字母{A,B,C,D,E}正在使用那么可能的1-4个字母组合是:A,B,C,D,E,AB,AC,AD, AE,BC,BD,BE,CD,CE,DE,ABC,ABD,ABE,ACD,ACE,ADE,BCD,BCE,BDE,CDE,ABCD,ABCE,ABDE,ACDE,BCDE

这是一个使用一组5个字母{A,B,C,D,E}的工作示例.

DDDDECBBBBAECCCCDAEEE EBDAAAACBDDB

第1到第4个元素组成集:D第2到第5个元素组成集:DE第3到第6个元素组成集:CDE第4到第7个元素组成集:BCDE第5到第8个元素组成集:BCE第6到第9个元素形成集合:BC第7到第10个元素形成集合:B等.

*我希望找到一个字符串的工作示例,该字符串使用12个不同的字母(在796个字母的字符串中总共793个4个字母的组)开始(如果可能的话结束)4个相同的字母.*

这是一个7个字母的工作解决方案:

AAAABCDBEAAACDECFAAADBFBACEAGAADEFBAGACDFBGCCCCDGEAFAGCBEEECGFFBFEGGGGFDEEEEFCBBBBGDCFFFFDAGBEGDDDDBE

Answer 1

很酷的问题。只是一个草稿/伪算法：

dim STR-A as string = getall(ABCDEFGHIJKL) 
//custom function to generate concat list of all 793 4-char combos.
//should be listed side-by-side to form 3172 character-long string.
//different ordering may ultimately produce different results.
//brute-forcing all orders of combos is too much work (793! is a big #).
//need to determine how to find optimal ordering, for this particular
//approach below.
dim STR-B as string = "" // to hold the string you're searching for  
dim STR-C as string = "" // to hold the sub-string you are searching in  
dim STR-A-NEW as string = "" //variable to hold your new string
dim MATCH as boolean = false //variable to hold matching status

while len(STR-A) > 0 
//check each character in STR-A, which will be shorted by 1 char on each
//pass.
  MATCH = false
  STR-B = left(STR-A, 4)
  STR-B = reduce(STR-B) 
  //reduce(str) is a custom re-usable function to sort & remove duplicates

  for i as integer = 1 to len((STR-A) - 1)
    STR-C = substr(STR-A, i, 4) 
    //gives you the 4-character sequence beginning at position i
    STR-C = reduce(STR-C)
    IF STR-B = STR-C Then
       MATCH = true
       exit for 
       //as long as there is even one match, you can throw-away the first 
       //letter
    END IF
    i = i+1
  next


  IF match = false then 
  //if you didn't find a match, then the first letter should be saved
     STR-A-NEW += LEFT(STR-B, 1)
  END IF

  MATCH = false //re-init MATCH
  STR-A = RIGHT(STR-A, LEN(STR-A) - 1) //re-init STR_A
wend

不管怎样——这可能会出现问题，你需要编写另一个函数来解析结果字符串（STR-A-NEW）以证明这是一个可行的答案......