simple recursion help

Hung Jung Lu hungjunglu at yahoo.com
Sun Oct 24 05:16:26 CEST 2004


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.

(2) I too googled for the name of the operation of the original
poster. One name I found is "string" (see
http://mathworld.wolfram.com/BallPicking.html). However, this name may
not be universally recognized.

(3) The functional version would be:

strings = lambda Xs, k: reduce(lambda r, i: [p + x for p in r for x
in Xs], range(k), [''])

print strings('abc', 2)

Hung Jung



More information about the Python-list mailing list