Wie kann man herausfinden, ob ein Array eine arithmetische Progression (Sequenz) enthält?

Question

Ich habe eine sortierte Reihe von Zahlen wie

1, 4, 5 , 6, 8

Wie kann man herausfinden, ob dieses Feld eine arithmetische Progression (Sequenz) enthält?

wie in diesem Beispiel

4,6,8

o

 4,5,6

Anmerkung: Die kleinste Zahl in der Folge ist 3

Answer 1

Sie können dieses Problem rekursiv lösen, indem Sie es in kleinere Probleme aufteilen, die da wären:

• Identifizieren Sie die Paare {1,4},{1,5}...{6,8}
• Suchen Sie für jedes Paar nach Sequenzen mit demselben Intervall

Erstellen Sie zunächst das Gerüst, um die Probleme zu lösen:

Dim number(7) As Integer
Dim result() As Integer
Dim numbers As Integer
Sub FindThem()
number(1) = 1
number(2) = 4
number(3) = 5
number(4) = 6
number(5) = 8
number(6) = 10
number(7) = 15
numbers = UBound(number)
ReDim result(numbers)
Dim i As Integer
For i = 1 To numbers - 2
    FindPairs i
Next
End Sub

Iterieren Sie nun über die Paare

Sub FindPairs(start As Integer)
    Dim delta As Integer
    Dim j As Integer
    result(1) = number(start)
    For j = start + 1 To numbers
        result(2) = number(j)
        delta = result(2) - result(1)
        FindMore j, 2, delta
    Next
End Sub

Nach und nach Sequenzen finden

Sub FindMore(start As Integer, count As Integer, delta As Integer)
    Dim k As Integer
    For k = start + 1 To numbers
        step = number(k) - result(count)
        result(count + 1) = number(k) ' should be after the if statement
                                      ' but here makes debugging easier
        If step = delta Then
            PrintSeq "Found ", count + 1
            FindMore k, count + 1, delta
        ElseIf step > delta Then ' Pointless to search further
            Exit Sub
        End If
    Next
End Sub

Dies ist nur ein Beispiel für die Ergebnisse

Sub PrintSeq(text As String, count As Integer)
    ans = ""
    For t = 1 To count
        ans = ans & "," & result(t)
    Next
    ans = text & " " & Mid(ans, 2)
    Debug.Print ans
End Sub

Ergebnisse

findthem
Found  1,8,15
Found  4,5,6
Found  4,6,8
Found  4,6,8,10
Found  5,10,15
Found  6,8,10

Edit: Oh, und natürlich MUSS die Anordnung sortiert sein!

HTH

Answer 2

Sicherlich ist dies nicht die optimale Lösung für Ihr Problem, aber Sie können Folgendes tun:

Iterieren Sie durch alle Zahlenpaare in Ihrem Array - jeweils 2 Zahlen definieren die arithmetische Sequenz vollständig, wenn wir davon ausgehen, dass sie das erste und zweite Progressionselement sind. Wenn Sie also diese 2 Zahlen kennen, können Sie weitere Progressionselemente konstruieren und überprüfen, ob sie in Ihrem Array enthalten sind.

Wenn Sie nur 3 Zahlen finden wollen, die eine arithmetische Progression bilden, dann können Sie durch alle Paare von nicht benachbarten Zahlen a[i] und a[j], j > i+1 iterieren und prüfen, ob ihr arithmetisches Mittel zum Array gehört - das können Sie mit binärer Suche auf dem Intervall ]i,j[ tun.

Answer 3

Zunächst gehe ich davon aus, dass Sie nur arithmetische Folgen von drei oder mehr Termen benötigen.

Ich würde vorschlagen, jede Nummer zu überprüfen a[i] als Beginn einer arithmetischen Folge, und a[i+n] als die nächste.

Da Sie nun die ersten beiden Begriffe in Ihrer Reihe haben, können Sie den nächsten finden. Wenn x der erste Term und y der zweite Term ist, lauten die Terme im Allgemeinen x + i*(y-x) , mit dem ersten Term bei i = 0. Der nächste Term ist x + 2*(y-x). Suchen Sie in Ihrer Matrix nach diesem Wert. Wenn dieser Wert in Ihrem Array enthalten ist, haben Sie eine arithmetische Folge von drei oder mehr Elementen!

Sie können mit i=3, i=4 usw. weitermachen, bis Sie zu einem Ergebnis kommen, das nicht in Ihrem Array enthalten ist.

Si l die Größe des Arrays ist, machen Sie dies für alle i von 0 bis l-2 und alle n de 0 a l-i-1

Die einzige große Einschränkung ist, dass in diesem Beispiel beide Sequenzen gefunden werden 4,6,8 wie auch 6,8 . Technisch gesehen handelt es sich bei beiden um arithmetische Folgen in Ihrer Reihe. Sie müssen genauer definieren, was Sie dort wollen. In Ihrem Fall könnte es trivial sein, einfach alle Reihenfolgen zu prüfen und zu eliminieren, die vollständig in anderen enthalten sind.

Answer 4

Die allgemeine Idee ist, ein Element als a_1 auszuwählen, dann ein beliebiges Element nach diesem als a_2, die Differenz zu berechnen und dann zu sehen, ob es danach noch andere Elemente gibt, die dieser Differenz entsprechen. Solange es mindestens 3 Elemente mit der gleichen Differenz gibt, betrachten wir es als eine Progression.

progression (A, n)
   for i = 1 ... n - 2
      a_1 = A[i]
      for j = i + 1 ... n - 1
         a_2 = A[j]
         d = a_2 - a_1
         S = [ i, j ]
         for k = j + 1 ... n
            if ( d == ( a[k] - a[S.last] ) )
               /* Append the element index to the sequence so far. */
               S += k
         if ( |s| > 2 )
            /* We define a progression to have at least 3 numbers. */
            return true
   return false

Man kann den Algorithmus so modifizieren, dass er jede Menge S speichert, bevor sie verloren geht, um alle Progressionen für das gegebene Array A zu berechnen. Der Algorithmus läuft in O(n^3), wenn man annimmt, dass das Anhängen an und das Abrufen des letzten Elements der Menge S in konstanter Zeit erfolgt.

Obwohl ich das Gefühl habe, dass es eine effizientere Lösung geben könnte...

Answer 5

Hier ist der Code in Swift 4:

extension Array where Element == Int {

    var isArithmeticSequence: Bool {
        let difference = self[1] - self[0]
        for (index, _) in self.enumerated() {
            if index < self.count-1 {
                if self[index + 1] - self[index] != difference {
                    return false
                }
            }
        }
        return true
    }

    var arithmeticSlices: [[Int]] {

        var arithmeticSlices = [[Int]]()
        var sliceSize = 3
        while sliceSize < self.count+1 {

            for (index, _) in self.enumerated() {

                if (index + sliceSize-1) <= self.count - 1 {

                    let currentSlice = Array(self[index...index + sliceSize-1])
                    if currentSlice.isArithmeticSequence {
                        arithmeticSlices.append(currentSlice)
                    }
                }
            }
            sliceSize+=1
        }
        return arithmeticSlices
    }
}

let A = [23, 24, 98, 1, 2, 5]
print(A.arithmeticSlices) // []

let B = [4, 7, 10, 4,5]
print(B.arithmeticSlices) //[[1, 2, 3], [2, 3, 4], [3, 4, 5], [1, 2, 3, 4], [2, 3, 4, 5], [1, 2, 3, 4, 5]]

let C = [4, 7, 10, 23, 11, 12, 13]
print(C.arithmeticSlices) // [[4, 7, 10], [11, 12, 13]]