All combinations of N elements

Published
by
Gustavo Niemeyer
on 2005-04-08
in Math, Python and Snippet
.

Here’s a snippet to compute all combinations of N elements over K positions.

3 Responses to “All combinations of N elements”

Feed for this Entry Trackback Address
  1. 1 Guyon Moree
    2005-04-11 at 05:59

    hey, that someone was me! thanks for the code.

    I don’t see a ‘border’ though ;)

    What I mean is that you take the border from the length of your list. At least that is what I think I see happening here.

    What I meant was having a list of possible characters like ['a','b',(..) 'z']. And then also give a ‘border’. Let’s say you give a border of 3. This will effectively give you all possible 3-character combinations of *all* given characters.

    I hope I explained this good enough, thanks again!

  2. 2 Gustavo Niemeyer
    2005-04-11 at 22:06

    Hello Guyon! I think I understand what you meant now. The algorithm is pretty much the same:

    def allcombinations(n):
    queue = [-1]
    while queue:
        i = queue[-1]+1
        if i == 26:
            queue.pop()
        else:
            queue[-1] = i
            yield [chr(97+j) for j in queue]
            if len(queue) < n:
                queue.append(-1)

    The total combinations is computed by:

    def total(n):
    return sum([26**i for i in range(1,n+1)])

    Which means 12356630 entries for n=5!!! Be careful. :-)

  3. 3 Anonymous
    2005-04-12 at 14:45

    This list is the sum of three cartesian products,
    here it is cheating a bit and not in exactly the same order.

    import probstat # probstat.sf.net
def total(mylist):
  for (n) in range(len(mylist)):
    for (item) in probstat.Cartesian([mylist]*(n+1)):
      yield item

    for the list [1,2,3] it does the cartesian product of [1,2,3]
    then [1,2,3] x [1,2,3] then [1,2,3] x [1,2,3] x [1,2,3]

Leave a Reply