String Verkettung Abfragen

Question

Ich habe eine Liste von Zeichen, sagen x in der Zahl, mit b[1], b[2], b[3] ... b[x] bezeichnet. Nach x,

• b[x+1] ist die Verkettung von b[1],b[2].... b[x] in dieser Reihenfolge. Ähnlich ist

• b[x+2] ist die Verkettung von b[2],b[3]....b[x],b[x+1].

• Also, im Grunde b[n] letzten Verkettung von Genommen wird x Bezug auf b[i], von rechts nach links.

• gegebene Parameter wie p und q als Abfragen, wie ich an, welches Zeichen unter b[1], b[2], b[3]..... b[x] tut der q^th Charakter b[p] entspricht herausfinden können?

Hinweis:x und b[1], b[2], b[3]..... b[x] ist für alle Abfragen festgelegt.

Ich versuchte Brute-Forcing, aber die String-Länge steigt exponentiell für große x. (X < = 100).

---

Beispiel:

• Wenn x=3,

  b[] = a, b, c, a b c, b c abc, c abc bcabc, abc bcabc cabcbcabc, //.... 
  //Spaces for clarity, only commas separate array elements 
  

• Also für eine Abfrage, wo p=7, q=5, Antwort zurückgegeben würde 3 (entsprechend Charakter 'c') sein.

Ich habe gerade Schwierigkeiten, die Mathe dahinter herauszufinden. Sprache ist kein Problem

Answer 1

Ich schrieb diese Antwort, als ich es herausfand, also bitte tragen Sie mit mir.

Wie Sie erwähnt haben, ist es viel einfacher, um herauszufinden, wo das Zeichen an b[p][q] unter den ursprünglichen x Zeichen kommt als b[p] für große p zu erzeugen. Um dies zu tun, werden wir eine Schleife verwenden, um zu ermitteln, woher der aktuelle b[p][q] stammt, und dabei zu reduzieren, bis es zwischen 1 und x ist, und q, bis es 1 ist.

Schauen wir uns ein Beispiel für x=3 zu sehen, ob wir eine Formel erhalten können:

p N(p) b[p] 
- ---- ---- 
1 1  a 
2 1  b 
3 1  c 
4 3  a b c 
5 5  b c abc 
6 9  c abc bcabc 
7 17 abc bcabc cabcbcabc 
8 31 bcabc cabcbcabc abcbcabccabcbcabc 
9 57 cabcbcabc abcbcabccabcbcabc bcabccabcbcabcabcbcabccabcbcabc 

Die Folge ist klar: N(p) = N(p-1) + N(p-2) + N(p-3), wo N(p) ist die Anzahl der Zeichen in der p-ten Element der b.Mit und x können Sie einfach Brute-Force berechnen alle N für den Bereich [1, p]. Dadurch können Sie herausfinden, welches vorherige Element von bb[p][q] stammt.

Um zu veranschaulichen, sagen x=3, p=9 und q=45.

1. Die Tabelle gibt über N(6)=9, N(7)=17 und N(8)=31. Seit 45>9+17 wissen Sie, dass b[9][45] von b[8][45-(9+17)] = b[8][19] stammt.
2. Fortsetzung iterativ/rekursiv, 19>9+5, also b[8][19] = b[7][19-(9+5)] = b[7][5].
3. Jetzt 5>N(4) aber 5<N(4)+N(5), so b[7][5] = b[5][5-3] = b[5][2].
4. b[5][2] = b[3][2-1] = b[3][1]
5. Seit 3 <= x haben wir unsere Abschlussbedingung und b[9][45] ist c von b[3].

So etwas kann sehr leicht entweder rekursiv oder iterativ gegeben Start p, q, x und b bis zu x berechnet werden. Meine Methode benötigt Array-Elemente, um N(p) für die gesamte Sequenz zu berechnen. Dies kann in einem Array oder im Stack zugewiesen werden, wenn rekursiv gearbeitet wird.

Hier ist eine Referenz-Implementierung in Vanille-Python (ohne externe Importe, obwohl numpy wahrscheinlich diese rationalisieren würde helfen):

def so38509640(b, p, q): 
    """ 
    p, q are integers. b is a char sequence of length x. 
    list, string, or tuple are all valid choices for b. 
    """ 
    x = len(b) 

    # Trivial case 
    if p <= x: 
     if q != 1: 
      raise ValueError('q={} out of bounds for p={}'.format(q, p)) 
     return p, b[p - 1] 

    # Construct list of counts 
    N = [1] * p 
    for i in range(x, p): 
     N[i] = sum(N[i - x:i]) 
    print('N =', N) 

    # Error check 
    if q > N[-1]: 
     raise ValueError('q={} out of bounds for p={}'.format(q, p)) 

    print('b[{}][{}]'.format(p, q), end='') 

    # Reduce p, q until it is p < x 
    while p > x: 
     # Find which previous element character q comes from 
     offset = 0 
     for i in range(p - x - 1, p): 
      if i == p - 1: 
       raise ValueError('q={} out of bounds for p={}'.format(q, p)) 
      if offset + N[i] >= q: 
       q -= offset 
       p = i + 1 
       print(' = b[{}][{}]'.format(p, q), end='') 
       break 
      offset += N[i] 
    print() 
    return p, b[p - 1] 

Aufruf so38509640('abc', 9, 45)

N = [1, 1, 1, 3, 5, 9, 17, 31, 57] 
b[9][45] = b[8][19] = b[7][5] = b[5][2] = b[3][1] 
(3, 'c') # <-- Final answer 

erzeugt In ähnlicher Weise für das Beispiel in der Frage, so38509640('abc', 7, 5) ergibt das erwartete Ergebnis:

N = [1, 1, 1, 3, 5, 9, 17] 
b[7][5] = b[5][2] = b[3][1] 
(3, 'c') # <-- Final answer 

Leider konnte ich keinen besseren Funktionsnamen finden :) Das ist einfach genug Code, der in Py2 und 3, trotz Unterschiede in der range Funktion/Klasse, genauso gut funktionieren sollte.

Ich wäre sehr gespannt, ob es eine nicht-iterative Lösung für dieses Problem gibt. Vielleicht gibt es eine Möglichkeit, dies zu tun, mit modularen Arithmetik oder etwas ...