Python: Generate all uniquely ordered lists of length N

Question

I want to exhaustively analyse subroutines for sorting small arrays and need a way to generate all uniquely ordered arrays of a particular length. In Python, that would be lists with non-negative integers as elements and preferably using smallest integers when possible. For example, N = 3:

[[0,0,0],
[0,0,1],
[0,1,0],
[0,1,1],
[0,1,2],
[0,2,1],
[1,0,0],
[1,0,1],
[1,0,2],
[1,1,0],
[1,2,0],
[2,0,1],
[2,1,0]]

[1,1,1] and [2,2,0] don't belong in the list above, because [0,0,0] and [1,1,0] respectively have the same relative order while using smaller integers.

Answer 1

This is a combination of (a) finding lists [k_1, ..., k_n] such that each k_i equals either k_(i-1) or k_(i-1)+1, and (b) finding the unique permutations of those lists.

The first can be done using a recursive function:

def combinations(n, k=0):
    if n > 1:
        yield from ([k] + res for i in (0, 1)
                              for res in combinations(n-1, k+i))
    else:
        yield [k]

For lists with n elements, there will be 2^(n-1) such combinations:

>>> list(combinations(2))
[[0, 0], [0, 1]]
>>> list(combinations(3))
[[0, 0, 0], [0, 0, 1], [0, 1, 1], [0, 1, 2]]
>>> list(combinations(4))
[[0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 2], [0, 1, 1, 1], [0, 1, 1, 2], [0, 1, 2, 2], [0, 1, 2, 3]]

Combine that with itertools.permutations and filter out duplicates to get the final result:

import itertools
def all_combinations(n):
    return (x for combs in combinations(n)
              for x in set(itertools.permutations(combs)))

Example:

>>> list(all_combinations(3))
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
>>> sum(1 for _ in all_combinations(4))
75
>>> sum(1 for _ in all_combinations(5))
541

Note: Generating all n! permutations and then filtering the duplicates can be very wasteful even for slightly larger values of n. There are smarter ways of generating only unique permutations that can be used instead of itertools.permutations, see e.g. here or here.

Answer 2

You could iterate over the cartesian product of the range, for each element use the relative order as a key, and store the pair (relative order, tuple) in a dictionary, finally return sorted:

def uniquely_ordered_list(n=3):
    def key(o):
        relative = ['equal'] + ['less' if a < b else ('greater' if a > b else 'equal') for a, b in product(o, repeat=2)]
        return tuple(relative)

    found = {}
    for ordering in product(range(n), repeat=n):
        if key(ordering) not in found:
            found[key(ordering)] = ordering

    return sorted(found.values())

Output

(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(0, 1, 2)
(0, 2, 1)
(1, 0, 0)
(1, 0, 1)
(1, 0, 2)
(1, 1, 0)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)

UPDATE

As suggested by @tobias_k you could use the following function as key:

def key(o):
    sign = lambda x: x / abs(x) if x else x
    return tuple([0] + [sign(a - b) for a, b in product(o, repeat=2)])

Answer 3

Here's another solution:

import numpy as np
from itertools import product, combinations

def rord(lst):
    ''' Maps the relative order of a list 'lst' to a unique string of 0, 1, and 2.

    Relative order is computed by converting the list 'sgns' of all 
    the values sgn(lst[i]-lst[j])+1, for i<j, i,j = 0,..., n-1,
    to a string.

    E.g. the lists [0, 0, 1], [0, 0, 2] and [1, 1, 2] have the same rord = '100'
    because lst[0] = lst[1], lst[0] < lst[1], lst[1] < lst[2] for all
    of them, so sgns = [1, 0, 0]
    '''
    sgns = np.sign([tup[0]-tup[1] for tup in combinations(lst, 2)]) + 1
    return ''.join(str(e) for e in sgns)  # return sgns.tostring() is faster


def uniq_rord_lst(n):
    '''Returns n-length sequences of integers 0,... n-1, with unique relative
    order. E.g. for n=2 returns [(0, 0), (0, 1), (1, 0)].
    '''
    seen_ro = set()
    result = []
    for comb in product(range(n), repeat=n):
        ro = rord(comb)
        if ro not in seen_ro:
            seen_ro.add(ro)
            result.append(comb)
    return result

Example:

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

>>> uniq_rord_lst(3)
[(0, 0, 0),
 (0, 0, 1),
 (0, 1, 0),
 (0, 1, 1),
 (0, 1, 2),
 (0, 2, 1),
 (1, 0, 0),
 (1, 0, 1),
 (1, 0, 2),
 (1, 1, 0),
 (1, 2, 0),
 (2, 0, 1),
 (2, 1, 0)]

Update: a faster one

def uniq_rord_lst(n):
    seen_ro = set()
    result = []
    for comb in product(range(n), repeat=n):
        ro = tuple(sorted(comb).index(x) for x in comb)
        if ro not in seen_ro:
            seen_ro.add(ro)
            result.append(comb)           
    return result