Längste zunehmende Teilfolge

Hier ist, wie einfach die längste zu-und abnehmende Folge in Mathematica:

 LIS[list_] := LongestCommonSequence[Sort[list], list];
 input={0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
 LIS[input]
 -1*LIS[-1*input]

Ausgabe:

{0, 2, 6, 9, 11, 15}
{12, 10, 9, 5, 3}

Mathematica hat auch LongestIncreasingSubsequence Funktion in der Combinatorica` Bibliothek. Wenn Sie nicht über Mathematica können Sie die Abfrage der WolframAlpha.

C++ O(nlogn) - Lösung

Gibt es auch eine O(nlogn) - Lösung, basierend auf einigen
Beobachtungen. Lassen Sie Ai,j die kleinste
möglich Schwanz aus alle erhöhen
untersequenzen der Länge j mit
die Elemente a₁, a₂, ... ,_i. Beachten Sie, dass für jede
insbesondere i, A_i,1, A_{i 2}, ... ,_i,j. Dies deutet darauf hin, dass, wenn
wir wollen die längste Teilfolge, die
endet mit ai + 1, brauchen wir nur zu schauen
für ein j, so dass Ai,j < ai + 1 < =
Ai,j + 1 und der Länge j + 1.
Beachten Sie, dass in diesem Fall Ai + 1,j + 1
wird gleich ai + 1, und alle Ai +
1,k ist gleich Ai,k für k!=j+1.
Darüber hinaus gibt es bei den meisten ein
Unterschied zwischen der eingestellten Ai und der
set Ai + 1, die durch diese verursacht werden
Suche. Da A immer bestellt
die Erhöhung um, und die operation
nicht diese Reihenfolge ändern, können wir
tun eine binäre Suche für jeden einzelnen a₁, a₂, ... ,_n.

Umsetzung C++ (O(nlogn) - Algorithmus)

#include <vector>
using namespace std;

/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
  vector<int> p(a.size());
  int u, v;

  if (a.empty()) return;

  b.push_back(0);

  for (size_t i = 1; i < a.size(); i++) {
      if (a[b.back()] < a[i]) {
          p[i] = b.back();
          b.push_back(i);
          continue;
      }

      for (u = 0, v = b.size()-1; u < v;) {
          int c = (u + v) / 2;
          if (a[b[c]] < a[i]) u=c+1; else v=c;
      }

      if (a[i] < a[b[u]]) {
          if (u > 0) p[i] = b[u-1];
          b[u] = i;
      }   
  }

  for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}

/* Example of usage: */
#include <cstdio>
int main()
{
  int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
  vector<int> seq(a, a+sizeof(a)/sizeof(a[0]));
  vector<int> lis;
        find_lis(seq, lis);

  for (size_t i = 0; i < lis.size(); i++)
      printf("%d ", seq[lis[i]]);
        printf("\n");    

  return 0;
}

Quelle: link

Habe ich umgeschrieben, die C++ Implementierung für Java vor einer Weile, und kann bestätigen es funktioniert. Vektor-alternative in python ist die Liste. Aber wenn Sie möchten, testen Sie es selbst, hier ist der link für die online-compiler mit Beispiel-Implementierung geladen: link

Beispiel Daten: { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }
und die Antwort: 1 3 4 5 6 7.

InformationsquelleAutor der Antwort Margus

Hier ist eine ziemlich Allgemeine Lösung:

• läuft in O(n log n) Zeit,
• Griffe erhöhen, nondecreasing, Verringerung und zum nonincreasing untersequenzen,
• arbeitet mit einer Sequenz von Objekten, einschließlich listnumpy.arraystr und mehr,
• unterstützt Listen von Objekten und benutzerdefinierten Vergleich der Methoden durch die key parameter funktioniert wie in dem builtin sorted Funktion,
• können wieder die Elemente der Teilfolge oder deren Indizes.

Code:

from bisect import bisect_left, bisect_right
from functools import cmp_to_key

def longest_subsequence(seq, mode='strictly', order='increasing',
                        key=None, index=False):

  bisect = bisect_left if mode.startswith('strict') else bisect_right

  # compute keys for comparison just once
  rank = seq if key is None else map(key, seq)
  if order == 'decreasing':
    rank = map(cmp_to_key(lambda x,y: 1 if x<y else 0 if x==y else -1), rank)
  rank = list(rank)

  if not rank: return []

  lastoflength = [0] # end position of subsequence with given length
  predecessor = [None] # penultimate element of l.i.s. ending at given position

  for i in range(1, len(seq)):
    # seq[i] can extend a subsequence that ends with a lesser (or equal) element
    j = bisect([rank[k] for k in lastoflength], rank[i])
    # update existing subsequence of length j or extend the longest
    try: lastoflength[j] = i
    except: lastoflength.append(i)
    # remember element before seq[i] in the subsequence
    predecessor.append(lastoflength[j-1] if j > 0 else None)

  # trace indices [p^n(i), ..., p(p(i)), p(i), i], where n=len(lastoflength)-1
  def trace(i):
    if i is not None:
      yield from trace(predecessor[i])
      yield i
  indices = trace(lastoflength[-1])

  return list(indices) if index else [seq[i] for i in indices]

Schrieb ich einen docstring für die Funktion, dass ich nicht fügen Sie oben, um zu zeigen, den code:

"""
Return the longest increasing subsequence of `seq`.

Parameters
----------
seq : sequence object
  Can be any sequence, like `str`, `list`, `numpy.array`.
mode : {'strict', 'strictly', 'weak', 'weakly'}, optional
  If set to 'strict', the subsequence will contain unique elements.
  Using 'weak' an element can be repeated many times.
  Modes ending in -ly serve as a convenience to use with `order` parameter,
  because `longest_sequence(seq, 'weakly', 'increasing')` reads better.
  The default is 'strict'.
order : {'increasing', 'decreasing'}, optional
  By default return the longest increasing subsequence, but it is possible
  to return the longest decreasing sequence as well.
key : function, optional
  Specifies a function of one argument that is used to extract a comparison
  key from each list element (e.g., `str.lower`, `lambda x: x[0]`).
  The default value is `None` (compare the elements directly).
index : bool, optional
  If set to `True`, return the indices of the subsequence, otherwise return
  the elements. Default is `False`.

Returns
-------
elements : list, optional
  A `list` of elements of the longest subsequence.
  Returned by default and when `index` is set to `False`.
indices : list, optional
  A `list` of indices pointing to elements in the longest subsequence.
  Returned when `index` is set to `True`.
"""

Einige Beispiele:

>>> seq = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

>>> longest_subsequence(seq)
[0, 2, 6, 9, 11, 15]

>>> longest_subsequence(seq, order='decreasing')
[12, 10, 9, 5, 3]

>>> txt = ("Given an input sequence, what is the best way to find the longest"
               " (not necessarily continuous) non-decreasing subsequence.")

>>> ''.join(longest_subsequence(txt))
' ,abdegilnorsu'

>>> ''.join(longest_subsequence(txt, 'weak'))
'              ceilnnnnrsssu'

>>> ''.join(longest_subsequence(txt, 'weakly', 'decreasing'))
'vuutttttttssronnnnngeee.'

>>> dates = [
...   ('2015-02-03', 'name1'),
...   ('2015-02-04', 'nameg'),
...   ('2015-02-04', 'name5'),
...   ('2015-02-05', 'nameh'),
...   ('1929-03-12', 'name4'),
...   ('2023-07-01', 'name7'),
...   ('2015-02-07', 'name0'),
...   ('2015-02-08', 'nameh'),
...   ('2015-02-15', 'namex'),
...   ('2015-02-09', 'namew'),
...   ('1980-12-23', 'name2'),
...   ('2015-02-12', 'namen'),
...   ('2015-02-13', 'named'),
... ]

>>> longest_subsequence(dates, 'weak')

[('2015-02-03', 'name1'),
 ('2015-02-04', 'name5'),
 ('2015-02-05', 'nameh'),
 ('2015-02-07', 'name0'),
 ('2015-02-08', 'nameh'),
 ('2015-02-09', 'namew'),
 ('2015-02-12', 'namen'),
 ('2015-02-13', 'named')]

>>> from operator import itemgetter

>>> longest_subsequence(dates, 'weak', key=itemgetter(0))

[('2015-02-03', 'name1'),
 ('2015-02-04', 'nameg'),
 ('2015-02-04', 'name5'),
 ('2015-02-05', 'nameh'),
 ('2015-02-07', 'name0'),
 ('2015-02-08', 'nameh'),
 ('2015-02-09', 'namew'),
 ('2015-02-12', 'namen'),
 ('2015-02-13', 'named')]

>>> indices = set(longest_subsequence(dates, key=itemgetter(0), index=True))

>>> [e for i,e in enumerate(dates) if i not in indices]

[('2015-02-04', 'nameg'),
 ('1929-03-12', 'name4'),
 ('2023-07-01', 'name7'),
 ('2015-02-15', 'namex'),
 ('1980-12-23', 'name2')]

Diese Antwort war zum Teil inspiriert durch die Frage zu Code-Review und zum Teil durch Frage zu Fragen über "out of sequence" Werten.

InformationsquelleAutor der Antwort arekolek

Hier ist der code und die Erklärung mit Java, kann ich hinzufügen, für python bald.

arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

1. Liste = {0} Initialisieren Liste auf die leere Menge
2. Liste = {0,8} - Neue größte LIS
3. Liste = {0, 4} - Verändert 8 4
4. Liste = {0, 4, 12} - Neue größte LIS
5. Liste = {0, 2, 12} - Geändert 4 2
6. Liste = {0, 2, 10} - Geändert 12 10
7. Liste = {0, 2, 6} - Verändert 10 bis 6
8. Liste = {0, 2, 6, 14} - Neue größte LIS
9. Liste = {0, 1, 6, 14} - Geändert von 2 auf 1
10. Liste = {0, 1, 6, 9} - Geändert 14 zu 9
11. Liste = {0, 1, 5, 9} - Geändert von 6 zu 5
12. Liste = {0, 1, 6, 9, 13} - Geändert von 3 auf 2
13. Liste = {0, 1, 3, 9, 11} - Neue größte LIS
14. Liste = {0, 1, 3, 9, 11} - Geändert von 9 bis 5
15. Liste = {0, 1, 3, 7, 11} - Neue größte LIS
16. Liste = {0, 1, 3, 7, 11, 15} - Neue größte LIS

So dass die Länge der LIS 6 (Größe der Liste).

import java.util.ArrayList;
import java.util.List;


public class LongestIncreasingSubsequence {
    public static void main(String[] args) {
        int[] arr = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
        increasingSubsequenceValues(arr);
    }

    public static void increasingSubsequenceValues(int[] seq) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < seq.length; i++) {
            int j = 0;
            boolean elementUpdate = false;
            for (; j < list.size(); j++) {
                if (list.get(j) > seq[i]) {
                    list.add(j, seq[i]);
                    list.remove(j + 1);
                    elementUpdate = true;
                    break;
                }
            }
            if (!elementUpdate) {
                list.add(j, seq[i]);
            }
        }
        System.out.println("Longest Increasing Subsequence" + list);
    }


}

Ausgang für den obigen code: Längsten Steigenden Teilfolge[0, 1, 3, 7, 11, 15]

InformationsquelleAutor der Antwort Deepak Singhvi

hier ist eine kompakte Umsetzung mit "auflisten"

def lis(l):

# we will create a list of lists where each sub-list contains
# the longest increasing subsequence ending at this index
lis = [[e] for e in l]
# start with just the elements of l as contents of the sub-lists

# iterate over (index,value) of l
for i, e in enumerate(l):
    # (index,value) tuples for elements b where b<e and a<i
    lower_tuples = filter(lambda (a,b): b<e, enumerate(l[:i]))
    # if no such items, nothing to do
    if not lower_tuples: continue
    # keep the lis-es of such items
    lowerlises = [lis[a] for a,b in  lower_tuples ]
    # choose the longest one of those and add
    # to the current element's lis
    lis[i] = max(lowerlises, key=len) + [e]

# retrun the longest of lis-es
return max(lis, key=len)

InformationsquelleAutor der Antwort cmantas