Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
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.011
X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; 'else:': 0.03; 'algorithm': 0.04; 'output': 0.05; 'cc:addr:python-list': 0.11; 'def': 0.12; '-1):': 0.16; 'cc:name:python list': 0.16; 'subject:combinations': 0.16; 'subject:generator': 0.16; 'wrote:': 0.18; 'verbal': 0.19; 'cc:addr:python.org': 0.22; 'cc:2**0': 0.24; 'this:': 0.26; 'asking': 0.27; 'header:In-Reply-To:1': 0.27; 'message- id:@mail.gmail.com': 0.30; "i'm": 0.30; 'code': 0.31; "i'd": 0.34; 'but': 0.35; 'received:google.com': 0.35; 'really': 0.36; 'yield': 0.36; 'subject:?': 0.36; 'should': 0.36; 'sure': 0.39; 'break': 0.61; 'john': 0.61; "you're": 0.61; 'such': 0.63; 'oscar': 0.84; '2013': 0.98
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:content-type; bh=ktSHBHUJ6J7+GUf2ApqgyIc0yIGN43G9fqvomzB02+E=; b=0BcLDoFnKLHDauFajUa/AbjHObnbZloMCPqYNGsWDuQsdOiqsUpYSIhwKrcmXyJFPq bB0Dgu/+x9HxihBVJe7odceWVODRHIfRY5MS8JGWguBiHrE/9eDLd63W4ui+9CTtOrMz MtDUNtUkriWFqMcvjcJvp6YpAHsPthASJVFDsg/tnhxwfpofqW/shBsdYqtP0c9HKKEQ REX8SPNYiIHKZi3TZ77xtb0bWPszXUQUwhmGLCXmPk36vQIOz5WiKb2nMXqNx15e8Djg SxSqAFKhOKAUhwm/TyT39CueuEzFZyqJpZ7l59a96PGmmyoJBr+zJpuVGYUeMK+Nx2YL 38dA==
X-Received: by 10.220.86.69 with SMTP id r5mr5518105vcl.9.1385034190558; Thu, 21 Nov 2013 03:43:10 -0800 (PST)
MIME-Version: 1.0
In-Reply-To: <20131121174614.53450d51@mini.home>
References: <20131121174614.53450d51@mini.home>
From: Oscar Benjamin <oscar.j.benjamin@gmail.com>
Date: Thu, 21 Nov 2013 11:42:49 +0000
Subject: Re: Recursive generator for combinations of a multiset?
To: "John O'Hagan" <research@johnohagan.com>
Content-Type: text/plain; charset=ISO-8859-1
Cc: Python List <python-list@python.org>
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
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>
Newsgroups: comp.lang.python
Message-ID: <mailman.3007.1385034193.18130.python-list@python.org>
Lines: 41
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1385034193 news.xs4all.nl 15952 [2001:888:2000:d::a6]:41279
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:60162

On 21 November 2013 06:46, John O'Hagan <research@johnohagan.com> wrote:
>
> I found a verbal description of such an algorithm and came up with
> this:
>
> def multicombs(it, r):
>     result = it[:r]
>     yield result
>     while 1:
>         for i in range(-1, -r - 1, -1):
>             rep = result[i]
>             if rep < it[i]:
>                 break
>         else:
>             break
>         for j, n in enumerate(it):
>             if n > rep:
>                 break
>         result = result[:i] + it[j:j - i]
>         yield result

I'm not really sure what it is you're asking for. I thought if I ran
the code I'd understand but that just confused me more. Is the output
below correct? If not what should it be?

multicombs("abracadabra", 0)
['']
multicombs("abracadabra", 1)
['a']
multicombs("abracadabra", 2)
['ab', 'br', 'ra']
multicombs("abracadabra", 3)
['abr', 'ara', 'bra']
multicombs("abracadabra", 4)
['abra']
multicombs("abracadabra", 5)
['abrac', 'abrbr', 'abrra', 'braca', 'brara', 'brbra', 'racad',
'racbr', 'racra']


Oscar