Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #107444

Re: Detecting repeated subsequences of identical items

Path csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From Oscar Benjamin <oscar.j.benjamin@gmail.com>
Newsgroups comp.lang.python
Subject Re: Detecting repeated subsequences of identical items
Date Thu, 21 Apr 2016 09:53:04 +0100
Lines 43
Message-ID <mailman.7.1461228807.23626.python-list@python.org> (permalink)
References <571843f9$0$1585$c3e8da3$5496439d@news.astraweb.com> <CAHVvXxTCQT0Tp3-Pd0O5mqSMDA6s=dqj+DDTpkq1AvYoCYs-7Q@mail.gmail.com>
Mime-Version 1.0
Content-Type text/plain; charset=UTF-8
X-Trace news.uni-berlin.de CD224aKjKBPJXuABdzXDIg+HE5M37NXmbcqWBto88dDA==
Return-Path <oscar.j.benjamin@gmail.com>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.004
X-Spam-Evidence '*H*': 0.99; '*S*': 0.00; 'python)': 0.05; 'repeated': 0.07; 'stack.': 0.07; 'cc:addr:python-list': 0.09; '2016': 0.16; 'cc:name:python list': 0.16; 'itertools': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'sequence.': 0.16; 'subject:Detecting': 0.16; 'to:addr:pearwood.info': 0.16; "to:name:steven d'aprano": 0.16; 'wrote:': 0.16; 'have:': 0.18; 'cc:2**0': 0.20; 'cc:addr:python.org': 0.20; 'import': 0.24; 'header:In-Reply-To:1': 0.24; 'skip:" 20': 0.26; 'message- id:@mail.gmail.com': 0.27; 'sequence': 0.27; 'function': 0.28; 'key,': 0.29; 'url:wikipedia': 0.29; 'url:wiki': 0.30; "d'aprano": 0.33; 'steven': 0.33; 'gets': 0.35; 'received:google.com': 0.35; 'next': 0.35; 'item': 0.35; 'there': 0.36; 'url:org': 0.36; 'received:209.85': 0.36; 'subject:: ': 0.37; 'two': 0.37; 'received:209': 0.38; 'url:en': 0.39; 'some': 0.40; 'your': 0.60; 'here:': 0.63; 'oscar': 0.84; 'abc': 0.91
DKIM-Signature v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=dMLOlSZ7W9yPEG0x6SKrLlDfCIvvIyN44AxlhfFu/OM=; b=YYI9/d/j+y0MTsudapVX0b4y8oZ5/OYJeCvut3uQ8zNUxk7ZAz81OLxoipODhO04+e KQpUpAGk66FKC+ji8XT/srNL137xT8v8OurGr0T/oFOOwbUSjWdiZ+cK8GS6GXZQfPvH 3QB7pU1MadsefBie1HIA7cG5Oa6I09c6Gm1JmTgx2G2WLkQbl4PvtOkjFP5DmQiTWu3N RWB0td6g9OUDidZ2/5fouxLcfmswQTFTxqgDGP0esKa/k6ZRw9q5Dc+Ht6WNtVjkYz3F 3SStbM/FMbJRVlX/lRlDBioX9VdKuBQ+udx3rTJ0TpnUbg6GUuikObqjl4CnSIfyff9s JScw==
X-Google-DKIM-Signature v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=dMLOlSZ7W9yPEG0x6SKrLlDfCIvvIyN44AxlhfFu/OM=; b=bePeC/9fuGXB9PJGZ6pKB8YX0/UVanNiSb9C5jKaPNH58dbVLe1P8LEE2nYnhJHoCu kl75qh9PAV/5cx/cIqUlsgWkTwAEvrh3sOQLjvcLY9KzA5+ZegFy1OMztI/7UCa0i5b0 EtpxVw64fDf9xUarjBBiN2qlBLovwYGpzFI8Ri+mKgqf6BykHuxxI22wXzA/RYlp+5XR aHHyRtn0DwohejarGGxOe11R3wuB8iwV90cuy0pY+OB9ZoWa7aY0nHJg9RucUSgez1U4 XxvzyFLwSNgpkqTdWhQNuJnbhWhhCKhbKf2lLWnlULPVFkKkb1ygVerDW2IkW5d6ccIf OGYQ==
X-Gm-Message-State AOPr4FXlacpFpf7bomaP+NHXHuCw0h1pUSU7w0XgaXa5mY/oNIsTiF61fms9BwxGBszLxHAt63v1WvRGCjEw/w==
X-Received by 10.112.16.36 with SMTP id c4mr5715778lbd.90.1461228804292; Thu, 21 Apr 2016 01:53:24 -0700 (PDT)
In-Reply-To <571843f9$0$1585$c3e8da3$5496439d@news.astraweb.com>
X-BeenThere python-list@python.org
X-Mailman-Version 2.1.22
Precedence list
List-Id General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive <http://mail.python.org/pipermail/python-list/>
List-Post <mailto:python-list@python.org>
List-Help <mailto:python-list-request@python.org?subject=help>
List-Subscribe <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
X-Mailman-Original-Message-ID <CAHVvXxTCQT0Tp3-Pd0O5mqSMDA6s=dqj+DDTpkq1AvYoCYs-7Q@mail.gmail.com>
X-Mailman-Original-References <571843f9$0$1585$c3e8da3$5496439d@news.astraweb.com>
Xref csiph.com comp.lang.python:107444

Show key headers only | View raw

On 21 April 2016 at 04:07, Steven D'Aprano <steve@pearwood.info> wrote:
> I want to group repeated items in a sequence. For example, I can group
> repeated sequences of a single item at a time using groupby:
>
>
> from itertools import groupby
> for key, group in groupby("AAAABBCDDEEEFFFF"):
>     group = list(group)
>     print(key, "count =", len(group))
>
>
> outputs:
>
> A count = 4
> B count = 2
> C count = 1
> D count = 2
> E count = 3
> F count = 4
>
>
> Now I want to group subsequences. For example, I have:
>
> "ABCABCABCDEABCDEFABCABCABCB"
>
> and I want to group it into repeating subsequences. I can see two ways to
> group it:
>
> ABC ABC ABCDE ABCDE F ABC ABC ABC B

There are some algorithms (helpfully shown in Python) here:

https://en.wikipedia.org/wiki/Cycle_detection

Note that those are for a sequence made as x[n+1] = f(x[n]) for some
function f. In your case that's just the function that gets the next
frame up/down in the call stack.

--
Oscar

--
Oscar

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Detecting repeated subsequences of identical items Steven D'Aprano <steve@pearwood.info> - 2016-04-21 13:07 +1000
  Re: Detecting repeated subsequences of identical items Ethan Furman <ethan@stoneleaf.us> - 2016-04-20 20:57 -0700
  Re: Detecting repeated subsequences of identical items Ethan Furman <ethan@stoneleaf.us> - 2016-04-20 21:15 -0700
  Re: Detecting repeated subsequences of identical items Chris Angelico <rosuav@gmail.com> - 2016-04-21 15:37 +1000
  Re: Detecting repeated subsequences of identical items Michael Selik <michael.selik@gmail.com> - 2016-04-21 06:35 +0000
    Re: Detecting repeated subsequences of identical items Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2016-04-21 18:05 +1000
      Re: Detecting repeated subsequences of identical items Nobody <nobody@nowhere.invalid> - 2016-04-21 13:02 +0100
  Re: Detecting repeated subsequences of identical items Michael Selik <michael.selik@gmail.com> - 2016-04-21 06:49 +0000
  Re: Detecting repeated subsequences of identical items Vlastimil Brom <vlastimil.brom@gmail.com> - 2016-04-21 08:54 +0200
  Re: Detecting repeated subsequences of identical items Michael Selik <michael.selik@gmail.com> - 2016-04-21 07:05 +0000
  Re: Detecting repeated subsequences of identical items Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2016-04-21 09:25 +0200
  Re: Detecting repeated subsequences of identical items Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2016-04-21 09:53 +0100
    Re: Detecting repeated subsequences of identical items Steven D'Aprano <steve@pearwood.info> - 2016-04-21 22:15 +1000
      Re: Detecting repeated subsequences of identical items Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2016-04-21 15:01 +0100
      Re: Detecting repeated subsequences of identical items Chris Angelico <rosuav@gmail.com> - 2016-04-22 00:12 +1000
        Re: Detecting repeated subsequences of identical items Steven D'Aprano <steve@pearwood.info> - 2016-04-23 01:00 +1000
      Re: Detecting repeated subsequences of identical items Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2016-04-21 15:30 +0100
      Re: Detecting repeated subsequences of identical items Chris Angelico <rosuav@gmail.com> - 2016-04-22 01:02 +1000
  Re: Detecting repeated subsequences of identical items Serhiy Storchaka <storchaka@gmail.com> - 2016-04-21 14:56 +0300

csiph-web