가장 길게 증가하는 서브 시퀀스

입력 시퀀스가 주어지면 가장 길지 않은 (연속적 일 필요는 없지만) 감소하지 않는 하위 시퀀스를 찾는 가장 좋은 방법은 무엇입니까?

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 # sequence

1, 9, 13, 15 # non-decreasing subsequence

0, 2, 6, 9, 13, 15 # longest non-deceasing subsequence (not unique)

나는 최고의 알고리즘을 찾고있다. 코드가 있다면 Python은 좋을 것이지만 아무 것도 괜찮습니다.

해결법

==============================
1.방금이 문제를 발견하고이 Python 3 구현을 생각해 냈습니다.

방금이 문제를 발견하고이 Python 3 구현을 생각해 냈습니다.
```
def subsequence(seq):
    if not seq:
        return seq

    M = [None] * len(seq)    # offset by 1 (j -> j-1)
    P = [None] * len(seq)

    # Since we have at least one element in our list, we can start by 
    # knowing that the there's at least an increasing subsequence of length one:
    # the first element.
    L = 1
    M[0] = 0

    # Looping over the sequence starting from the second element
    for i in range(1, len(seq)):
        # Binary search: we want the largest j <= L
        #  such that seq[M[j]] < seq[i] (default j = 0),
        #  hence we want the lower bound at the end of the search process.
        lower = 0
        upper = L

        # Since the binary search will not look at the upper bound value,
        # we'll have to check that manually
        if seq[M[upper-1]] < seq[i]:
            j = upper

        else:
            # actual binary search loop
            while upper - lower > 1:
                mid = (upper + lower) // 2
                if seq[M[mid-1]] < seq[i]:
                    lower = mid
                else:
                    upper = mid

            j = lower    # this will also set the default value to 0

        P[i] = M[j-1]

        if j == L or seq[i] < seq[M[j]]:
            M[j] = i
            L = max(L, j+1)

    # Building the result: [seq[M[L-1]], seq[P[M[L-1]]], seq[P[P[M[L-1]]]], ...]
    result = []
    pos = M[L-1]
    for _ in range(L):
        result.append(seq[pos])
        pos = P[pos]

    return result[::-1]    # reversing
```
알고리즘 작동 방식을 이해하는 데 어느 정도 시간이 걸렸으므로 설명이 약간 자세 했으므로 간단한 설명을 추가하겠습니다.

알고리즘 작동 방식 :

참고 : 위키피디아 알고리즘과의 유일한 차이점은 M 목록에서 오프셋 1이고 X는 여기에서 seq입니다. 나는 또한 Eric Gustavson 대답에서 보여준 것의 약간 개선 된 단위 테스트 버전으로 테스트하고 모든 테스트를 통과했다.

예:
```
seq = [30, 10, 20, 50, 40, 80, 60]

       0    1   2   3   4   5   6   <-- indexes
```
결국 우리는 다음을 갖게 될 것입니다.
```
M = [1, 2, 4, 6, None, None, None]
P = [None, None, 1, 2, 2, 4, 4]
result = [10, 20, 40, 60]
```
보시다시피 P는 매우 간단합니다. 우리는 마지막부터 살펴 봐야하기 때문에 60 이전에는 40, 80은 40, 40은 20, 50은 20, 20은 10이됩니다.

복잡한 부분은 M에있다. 길이 1의 서브 시퀀스의 마지막 요소 (따라서 M에서의 위치 0)가 색인 0 : 30에 있었기 때문에 처음에는 M이 [0, 없음, 없음, ...]이었다.

이 시점에서 우리는 seq를 반복하고 10을 봅니다. 10은 30보다 작으므로 M은 업데이트됩니다.
```
if j == L or seq[i] < seq[M[j]]:
    M[j] = i
```
이제 M은 다음과 같이 보입니다 : [1, None, None, ...]. 이는 더 좋은 결과입니다. 왜냐하면 10은 더 긴 부분 시퀀스를 만드는 더 많은 chanches를 가지고 있기 때문입니다. (새로운 1은 10의 지수입니다)

이제는 20의 차례입니다. 10과 20에 길이 2의 하위 시퀀스 (인덱스 1 : M)가 있으므로 M은 [1, 2, 없음, ...]입니다. (새로운 2는 20의 색인입니다)

이제는 50 세가되었습니다. 50은 아무런 변화가 없으므로 어떤 하위 서열에도 속하지 않습니다.

10, 20, 40으로 길이 3의 하위가 있습니다. (인덱스 2는 M이므로 M은 [1, 2, 4, 없음, ...]입니다. (새로운 4는 다음과 같습니다. 40의 지수)

등등...

코드 전체를 살펴 보려면 여기에 복사하여 붙여 넣을 수 있습니다. :)
==============================
2.다음은 Mathematica에서 가장 길게 늘리거나 줄이는 하위 시퀀스를 찾는 방법입니다.

다음은 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]
```
산출:
```
{0, 2, 6, 9, 11, 15}
{12, 10, 9, 5, 3}
```
Mathematica는 또한 Combinatorica` libary에서 LongestIncreasingSubsequence 함수를 사용합니다. Mathematica를 가지고 있지 않다면 WolframAlpha를 질의 할 수 있습니다.

출처 : 링크

나는 자바로 C ++ 구현을 얼마전에 다시 작성했으며, 그것이 작동하는지 확인할 수있다. 파이썬에서 벡터 대체 목록입니다. 하지만 직접 테스트하고 싶다면 여기에 예제 컴파일러가로드 된 온라인 컴파일러 링크가있다 : link

데이터 예 : {1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 답 : 1 3 4 5 6 7.

==============================

3.다음은 O (n * log (n))에서 실행되는 알고리즘을 구현하는 테스트와 함께 파이썬 코드입니다. 가장 길게 증가하는 서브 시퀀스에 대한 위키피디아 대화 페이지에서 이것을 발견했습니다.

다음은 O (n * log (n))에서 실행되는 알고리즘을 구현하는 테스트와 함께 파이썬 코드입니다. 가장 길게 증가하는 서브 시퀀스에 대한 위키피디아 대화 페이지에서 이것을 발견했습니다.

import unittest


def LongestIncreasingSubsequence(X):
    """
    Find and return longest increasing subsequence of S.
    If multiple increasing subsequences exist, the one that ends
    with the smallest value is preferred, and if multiple
    occurrences of that value can end the sequence, then the
    earliest occurrence is preferred.
    """
    n = len(X)
    X = [None] + X  # Pad sequence so that it starts at X[1]
    M = [None]*(n+1)  # Allocate arrays for M and P
    P = [None]*(n+1)
    L = 0
    for i in range(1,n+1):
        if L == 0 or X[M[1]] >= X[i]:
            # there is no j s.t. X[M[j]] < X[i]]
            j = 0
        else:
            # binary search for the largest j s.t. X[M[j]] < X[i]]
            lo = 1      # largest value known to be <= j
            hi = L+1    # smallest value known to be > j
            while lo < hi - 1:
                mid = (lo + hi)//2
                if X[M[mid]] < X[i]:
                    lo = mid
                else:
                    hi = mid
            j = lo

        P[i] = M[j]
        if j == L or X[i] < X[M[j+1]]:
            M[j+1] = i
            L = max(L,j+1)

    # Backtrack to find the optimal sequence in reverse order
    output = []
    pos = M[L]
    while L > 0:
        output.append(X[pos])
        pos = P[pos]
        L -= 1

    output.reverse()
    return output

# Try small lists and check that the correct subsequences are generated.

class LISTest(unittest.TestCase):
    def testLIS(self):
        self.assertEqual(LongestIncreasingSubsequence([]),[])
        self.assertEqual(LongestIncreasingSubsequence(range(10,0,-1)),[1])
        self.assertEqual(LongestIncreasingSubsequence(range(10)),range(10))
        self.assertEqual(LongestIncreasingSubsequence(\
            [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]), [1,2,3,5,8,9])

unittest.main()

==============================

4.다음은 꽤 일반적인 해결책입니다.

다음은 꽤 일반적인 해결책입니다.

코드:

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]

위의 코드를 보여주기 위해 위에 붙여 넣지 않은 함수에 대한 docstring을 작성했습니다.

"""
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`.
"""

몇 가지 예 :

>>> 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')]

이 답변은 부분적으로 코드 검토에서의 질문과 부분적으로 "순서가 틀린"값에 대해 묻는 질문에서 영감을 받았습니다.

==============================

5.

    int[] a = {1,3,2,4,5,4,6,7};
    StringBuilder s1 = new StringBuilder();
    for(int i : a){
     s1.append(i);
    }       
    StringBuilder s2 = new StringBuilder();
    int count = findSubstring(s1.toString(), s2);       
    System.out.println(s2.reverse());

public static int findSubstring(String str1, StringBuilder s2){     
    StringBuilder s1 = new StringBuilder(str1);
    if(s1.length() == 0){
        return 0;
    }
    if(s2.length() == 0){
        s2.append(s1.charAt(s1.length()-1));
        findSubstring(s1.deleteCharAt(s1.length()-1).toString(), s2);           
    } else if(s1.charAt(s1.length()-1) < s2.charAt(s2.length()-1)){ 
        char c = s1.charAt(s1.length()-1);
        return 1 + findSubstring(s1.deleteCharAt(s1.length()-1).toString(), s2.append(c));
    }
    else{
        char c = s1.charAt(s1.length()-1);
        StringBuilder s3 = new StringBuilder();
        for(int i=0; i < s2.length(); i++){
            if(s2.charAt(i) > c){
                s3.append(s2.charAt(i));
            }
        }
        s3.append(c);
        return Math.max(findSubstring(s1.deleteCharAt(s1.length()-1).toString(), s2), 
                findSubstring(s1.deleteCharAt(s1.length()-1).toString(), s3));
    }       
    return 0;
}

==============================

6.다음은 Java 코드 및 설명입니다. 곧 Python을 추가 할 것입니다.

다음은 Java 코드 및 설명입니다. 곧 Python을 추가 할 것입니다.

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

따라서 LIS의 길이는 6입니다 (목록의 크기).

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);
    }


}

위의 코드에 대한 출력 : Longest Increasing Subsequence [0, 1, 3, 7, 11, 15]

==============================
7.가장 효율적인 알고리즘은 여기에 설명 된 O (NlogN)입니다.

가장 효율적인 알고리즘은 여기에 설명 된 O (NlogN)입니다.

이 문제를 해결하는 또 다른 방법은 원래 배열의 가장 긴 공통 부분 시퀀스 (LCS)를 가져 오는 것이며 O (N2) 시간이 걸린 정렬 된 버전입니다.

==============================

8.다음은 "enumerate"를 사용하는 간결한 구현입니다.

다음은 "enumerate"를 사용하는 간결한 구현입니다.

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)

==============================

9.보다 작지만 효율적인 Python 구현은 다음과 같습니다.

보다 작지만 효율적인 Python 구현은 다음과 같습니다.

def longest_increasing_subsequence_indices(seq):
    from bisect import bisect_right

    if len(seq) == 0:
        return seq

    # m[j] in iteration i is the last index of the increasing subsequence of seq[:i]
    # that ends with the lowest possible value while having length j
    m = [None] * len(seq)
    predecessor = [None] * len(seq)
    best_len = 0

    for i, item in enumerate(seq):
        j = bisect_right([seq[k] for k in m[:best_len]], item)
        m[j] = i
        predecessor[i] = m[j-1] if j > 0 else None
        best_len = max(best_len, j+1)

    result = []
    i = m[best_len-1]
    while i is not None:
        result.append(i)
        i = predecessor[i]
    result.reverse()
    return result

def longest_increasing_subsequence(seq):
    return [seq[i] for i in longest_increasing_subsequence_indices(seq)]

from https://stackoverflow.com/questions/3992697/longest-increasing-subsequence by cc-by-sa and MIT license

'PYTHON' 카테고리의 다른 글

[PYTHON] datetime.isocalendar ()의 역함수를 찾는 가장 좋은 방법은 무엇입니까? (0)	2018.10.08
[PYTHON] 파이썬 프라임 번호 검사기 [duplicate] (0)	2018.10.08
[PYTHON] 양식 전송 오류, 플라스크 (0)	2018.10.08
[PYTHON] python selenium 버튼을 클릭하십시오. (0)	2018.10.08
[PYTHON] 파이썬에서 BOM 문자로 유니 코드 파일 데이터 읽기 (0)	2018.10.08

복붙노트

[PYTHON] 가장 길게 증가하는 서브 시퀀스

가장 길게 증가하는 서브 시퀀스

해결법

1.방금이 문제를 발견하고이 Python 3 구현을 생각해 냈습니다.

2.다음은 Mathematica에서 가장 길게 늘리거나 줄이는 하위 시퀀스를 찾는 방법입니다.

3.다음은 O (n * log (n))에서 실행되는 알고리즘을 구현하는 테스트와 함께 파이썬 코드입니다. 가장 길게 증가하는 서브 시퀀스에 대한 위키피디아 대화 페이지에서 이것을 발견했습니다.

4.다음은 꽤 일반적인 해결책입니다.

5.

6.다음은 Java 코드 및 설명입니다. 곧 Python을 추가 할 것입니다.

7.가장 효율적인 알고리즘은 여기에 설명 된 O (NlogN)입니다.

8.다음은 "enumerate"를 사용하는 간결한 구현입니다.

9.보다 작지만 효율적인 Python 구현은 다음과 같습니다.

'PYTHON' 카테고리의 다른 글

티스토리툴바