Generate All Possible Permutations (Or N-Tuples)

Generate all possible permutations (or n-tuples)

how about this:

tmp = expand.grid(1:2,1:2,1:2,1:2,1:2,1:2,1:2,1:2,1:2,1:2)

or this (thanks Tyler):

x <- list(1:2)
tmp = expand.grid(rep(x, 10))

How can i get ALL combination of different TUPLES of n-elements from a list of objects?

I think you want combinations, not permuatations. Permutations means the order of players matters.

Using an extension method you can generate the combinations:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k) {
    return k == 0 ? new[] { new T[0] } :
      elements.SelectMany((e, i) =>
        elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] { e }).Concat(c)));
}

So, for your sample problem, setup the parameters:

var N = 14;
var NumTeams = 3;
var NumPlayersPerTeam = 3;

First you can generate all the players:

var players = Enumerable.Range(1, N);

Then you can get every possible team, by combining the players NumPlayersPerTeam at a time:

var AllTeams = players.Combinations(NumPlayersPerTeam);

Then you can get all the sets of teams, by combining the teams NumTeams at a time:

var PossibleTeamSets = AllTeams.Combinations(NumTeams);

Flat permutations of n-tuple (breadth first)

Let seq(n, k) yield the sequence you want with k digits per entry, with digits from 0 to n.

Let step i be the phase that generates all tuples where the maximum digit is i.

At each step, we simply generate the i+1-ary representation of all the numbers up to (i+1) ** (k - 1) - 1 (i.e. up to k-1 digits). For each i+1-ary representation, we then produce the elements of the sequence by inserting the digit i at each location in the i+1-ary representation.

In order to avoid duplicates, we break early in the case we encounter an i already in the i+1-ary representation.

Here is an (ugly!) sample implementation in python:

def to_nary_string(num, n):
    if num == 0:
        return "0"

    result = ""
    while num != 0:
        result = str(num % n) + result
        num /= n

    return result

def seq(n, k):
    print "0" * k

    for i in range(2, n+2):
        for x in range(i**(k-1)):
            stem = to_nary_string(x, i).zfill(k-1)
            c = str(i-1)
            for j in range(k):
                print stem[:j] + c + stem[j:],               
                if j != k-1 and stem[j] == c:
                    break
        print

EDIT: The problem with this is that the k-1 digit strings have to be in the same order as the tuples, not sequential n-ary order. Changing the function slightly gives the desired result:

# Original list and string version
def seq(n, k):
    if (k == 0):
        return [""]

    result = []

    for i in range(n+1):
        c = str(hex(i))[2:] # 10 -> a, 11-> b, etc.

        for subseq in seq(i, k-1):
            for j in range(k):
                result.append(subseq[:j] + c + subseq[j:])
                if j != k-1 and subseq[j] == c:
                    break

    return result

Also, thanks to Claudiu, here is a generator and tuple version

# Generator and tuple version
#
# Thanks Claudiu!

def seq(n, k):
    if (k == 0):
        yield ()
        return

    for i in range(n+1):
        for subseq in seq(i, k-1):
            for j in range(k):
                yield subseq[:j] + (i,) + subseq[j:]
                if j != k-1 and subseq[j] == i:
                    break

Result (Line breaks added for clarity):

>>> for x in seq(4, 2):
    print x,

00
10 01 11
20 02 21 12 22
30 03 31 13 32 23 33
40 04 41 14 42 24 43 34 44

>>> for x in seq(3, 3):
    print x,

000
100 010 001
110 101 011
111
200 020 002
210 120 102 201 021 012
211 121 112
220 202 022
221 212 122
222
300 030 003
310 130 103 301 031 013
311 131 113
320 230 203 302 032 023
321 231 213 312 132 123
322 232 223
330 303 033
331 313 133
332 323 233
333

And a quick sanity check:

>>> len(seq(12, 4)) == 13 ** 4
True

How do I generate all permutations of a list?

Use itertools.permutations from the standard library:

import itertools
list(itertools.permutations([1, 2, 3]))

---

Adapted from here is a demonstration of how itertools.permutations might be implemented:

def permutations(elements):
    if len(elements) <= 1:
        yield elements
        return
    for perm in permutations(elements[1:]):
        for i in range(len(elements)):
            # nb elements[0:1] works in both string and list contexts
            yield perm[:i] + elements[0:1] + perm[i:]

A couple of alternative approaches are listed in the documentation of itertools.permutations. Here's one:

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[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

And another, based on itertools.product:

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

Generate all possible tuples combinations of given size for given range of values

With repetitions:

>>> from itertools import product
>>> list(product(range(1, 6), repeat=2))
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)]

Without repetitions:

>>> from itertools import permutations
>>> list(permutations(range(1, 6), 2))
[(1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4)]

Generate all 4-tuple pairs from n elements

You're doing a lot of unnecessary work by generating all pairs of combinations, and then discarding almost all of them because they contain common elements.

The following addresses this by first taking all subsets of four numbers (in your 2-tuple example), and then splitting each into all possible pairs:

import itertools

def gen_pairs(n, m):
  for both_halves in itertools.combinations(xrange(1, n + 1), 2 * m):
    for first_half in itertools.combinations(both_halves, m):
      second_half = tuple(sorted(set(both_halves) - set(first_half)))
      yield [first_half, second_half]

print sorted(gen_pairs(5, 2))

Note that this does not eliminate duplicates (for example, [(4, 5) (2, 3)] vs [(2, 3), (4, 5)]) and thus produces twice the number of elements you expect.

It is trivial to remove the duplicates, however. This is left as an exercise for the reader.

Generate all length-n permutations of True/False?

Use itertools.product:

>>> import itertools
>>> l = [False, True]
>>> list(itertools.product(l, repeat=3))
[(False, False, False), (False, False, True), (False, True, False), (False, True, True), (True, False, False), (True, False, True), (True, True, False), (True, True, True)]
>>> 

And if you want the to change the tuples inside the list to sublists, try a list comprehension:

>>> import itertools
>>> l = [False, True]
>>> [list(i) for i in itertools.product(l, repeat=3)]
[[False, False, False], [False, False, True], [False, True, False], [False, True, True], [True, False, False], [True, False, True], [True, True, False], [True, True, True]]
>>> 

Algorithm for generating n-tuples of an m-set

Here is a possible solution:

(define (append-all lst lst-of-lst)
  (if (empty? lst)
      '()
      (append (map (lambda (l) (cons (car lst) l)) lst-of-lst)
              (append-all (cdr lst) lst-of-lst))))

(define (generate-tuples lst n)
  (cond ((= n 0) '())
        ((= n 1) (map list lst))
        (else (let ((tuples (generate-tuples lst (- n 1))))
                (append-all lst tuples)))))

(generate-tuples '(+ -) 3)

'((+ + +) (+ + -) (+ - +) (+ - -) (- + +) (- + -) (- - +) (- - -))

The function append-all takes a list and a list of lists, and concatenate each element of the first list, in turn, with all the lists of the second parameter, and return the list of the results.

The terminal cases of the second function are, for n = 0, simply the empty list, for n = 1 a list constituted by the singleton lists containings the elements of the first parameter. When it recurs, first it produces the result with n-1 elements, then concatenated at the beginning of all those lists all the elements of the first parameter, in turn, by calling append-all.

How to construct a list of tuples of all possible combinations

Here's the proper way to use itertools to get what you want:

list(itertools.product(range(3), repeat=3))

The output is:

[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), (0, 1, 1),
 (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (1, 0, 0),
 (1, 0, 1), (1, 0, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2),
 (1, 2, 0), (1, 2, 1), (1, 2, 2), (2, 0, 0), (2, 0, 1),
 (2, 0, 2), (2, 1, 0), (2, 1, 1), (2, 1, 2), (2, 2, 0),
 (2, 2, 1), (2, 2, 2)]

Of course, this can scale up by using values other than 3. In general:

list(itertools.product(range(x), repeat=x))

will work for any x.

---

Related Topics