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

Groups > comp.lang.python > #60162

Re: Recursive generator for combinations of a multiset?

Show key headers only | View raw

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

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

Thread

Re: Recursive generator for combinations of a multiset? Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-11-21 11:42 +0000

csiph-web