# Combination generator

**URL:** <https://boards.straightdope.com/t/combination-generator/710404>\
**Category:** Factual Questions\
**Created:** [January 20, 2015, 7:41pm UTC](https://boards.straightdope.com/t/combination-generator/710404 "2015-01-20T19:41:18Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![VunderBob](https://avatars.discourse-cdn.com/v4/letter/v/839c29/32.png) [@VunderBob](https://boards.straightdope.com/u/VunderBob)\
**Post date:** [January 20, 2015, 7:41pm UTC](https://boards.straightdope.com/t/combination-generator/710404/1 "2015-01-20T19:41:18Z")

</div>

This is not, repeat not, a homework problem.

I am looking for a way to generate a table of coefficients for a program I am working on, such that the significance of the table is the order of the coefficients. As an example, say I start with an array {4, 3, 2, 1, 0}. In the process of ordering the array to {0, 1, 2, 3, 4}, I get every possible intermediate order combination.

I made a half assed attempt to do this with a bubble sort, but when the program was over, I had about a dozen or so intermediates (didn’t count), when I was expecting 120 (5!).

Any help out there, either with a walk through of the algorithm, or maybe even a code snippet?

---

<div class="post-metadata">

**Author:** ![md2000](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@md2000](https://boards.straightdope.com/u/md2000)\
**Post date:** [January 20, 2015, 8:09pm UTC](https://boards.straightdope.com/t/combination-generator/710404/2 "2015-01-20T20:09:43Z")

</div>

For n = 0 to 4  
For m = 0 to 4  
if m\<\> n then for a = 0 to 4  
if (m\<\>a and n\<\>a) then for b = 0 to 4  
if (m\<\>b and n\<\>b and a \<\>b) then for c = 0 to 4  
If c\<\>n and c\<\>m and c\<\>a and c\<\>b) then  
print n,m,a,b,c

Brute force and not exactly scalable.

---

<div class="post-metadata">

**Author:** ![VunderBob](https://avatars.discourse-cdn.com/v4/letter/v/839c29/32.png) [@VunderBob](https://boards.straightdope.com/u/VunderBob)\
**Post date:** [January 20, 2015, 8:20pm UTC](https://boards.straightdope.com/t/combination-generator/710404/3 "2015-01-20T20:20:13Z")

</div>

Thanks. I’ll play with that.

---

<div class="post-metadata">

**Author:** ![Lance\_Turbo](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lance_turbo/32/6156_2.png) [@Lance\_Turbo](https://boards.straightdope.com/u/Lance_Turbo)\
**Post date:** [January 20, 2015, 8:42pm UTC](https://boards.straightdope.com/t/combination-generator/710404/4 "2015-01-20T20:42:27Z")

</div>

Are you using Python?

If yes it’s easy.

```auto

import itertools as it

n = 5

for perm in it.permutations(range(n)):
    print(perm)

```

Even if you’re not using Python you can look up how it’s done in the [itertools documentation](https://docs.python.org/2/library/itertools.html#itertools.permutations).

```auto

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool* for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles* -= 1
            if cycles* == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles* = n - i
            else:
                j = cycles*
                indices*, indices[-j] = indices[-j], indices*
                yield tuple(pool* for i in indices[:r])
                break
        else:
            return

```