simple recursion help

[Thorsten Kampe]

* Hung Jung Lu (2004-10-24 04:16 +0100)
> Steven Bethard <steven.bethard at gmail.com> wrote:
>> Does anyone know what this operation is called?  It's not permutations or
>> combinations as I understand them since permutations and combinations do
>> not allow repetition.  I assume there was already a solution for this
>> somewhere, but I didn't know what term to google for.
> ---------------------------------------------------
> aleaxit at yahoo.com (Alex Martelli) wrote:
>> There's been a recent thread where the OP called them 'permutations',
>> somebody commented they're 'variations'.  In that thread you'll find a
>> bazillion solutions, recursive and non, with or without itertools, &c.
> ---------------------------------------------------
> 
> (1) "Variation" is the same as "permutation". It's matter of
> semantics. Some people use the notation V(n, k), some people use the
> notation P(n, k). For people that use the term "variation", the term
> "permutation" is reserved for the special case V(n, n). Neither name
> is right for the original question.

Well in fact it's a variation with repetition of the length 3 (or the
cartesian product "['a', 'b', 'c'] ** 3").

With the cvp[1] utility you could generate that like:
>>> l = ['a', 'b', 'c']
>>> util.cvp(l, 3, '#vr') # make sure it doesn't grow too big
27
>>> util.cvp(l, 3, 'vr')
[['a', 'a', 'a'],
 ['a', 'a', 'b'],
 ['a', 'a', 'c'],
 ['a', 'b', 'a'],
 ['a', 'b', 'b'],
 ['a', 'b', 'c'],
 ['a', 'c', 'a'],
 ['a', 'c', 'b'],
 ['a', 'c', 'c'],
 ['b', 'a', 'a'],
 ['b', 'a', 'b'],
 ['b', 'a', 'c'],
 ['b', 'b', 'a'],
 ['b', 'b', 'b'],
 ['b', 'b', 'c'],
 ['b', 'c', 'a'],
 ['b', 'c', 'b'],
 ['b', 'c', 'c'],
 ['c', 'a', 'a'],
 ['c', 'a', 'b'],
 ['c', 'a', 'c'],
 ['c', 'b', 'a'],
 ['c', 'b', 'b'],
 ['c', 'b', 'c'],
 ['c', 'c', 'a'],
 ['c', 'c', 'b'],
 ['c', 'c', 'c']]

Or like that:
>>> util.cartes(util.cartes(l, l), l, 'triple')

Thorsten

[1] cvp = "combinations, variations and permutations"
    http://www.thorstenkampe.de/python/util.py