Recursive generator for combinations of a multiset?

[Oscar Benjamin]

On 21 November 2013 06:46, John O'Hagan <research at 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