Python: генерировать все однозначно упорядоченные списки длины N

Question

Я хочу провести тщательный анализ подпрограмм для сортировки небольших массивов, и мне нужен способ для генерации всех уникально упорядоченных массивов определенной длины.В Python это были бы списки с неотрицательными целыми числами в качестве элементов и предпочтительно с использованием наименьших целых чисел, когда это возможно.Например, 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] и [2,2,0] не входят в вышеприведенный список, потому что [0,0,0] и [1,1,0] соответственно имеют одинаковый относительный порядок при использовании меньших целых чисел.

Answer 1

Вы можете перебрать декартово произведение диапазона, для каждого элемента использовать относительный порядок в качестве ключа и сохранить пару (относительный порядок, кортеж) в словаре, наконец, вернуть отсортированный:

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())

Вывод

(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)

ОБНОВЛЕНИЕ

В соответствии с предложением @tobias_k вы можете использовать следующую функцию в качестве клавиши:

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 2

Вот еще одно решение:

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

Пример:

>>> 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)]

Обновление : более быстрое

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

Answer 3

Это комбинация (а) поиска списков [k_1, ..., k_n], так что каждый k_i равен либо k_(i-1) или k_(i-1)+1, и (б) нахождения уникальных перестановок этих списков.

Первое можно сделать с помощью рекурсивной функции:

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]

Для списков с n элементами будет 2^(n-1) таких комбинаций:

>>> 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]]

Объедините это с itertools.permutations и отфильтруйте дубликаты, чтобы получить окончательный результат:

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

Пример:

>>> 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

Примечание: Генерация всех n! перестановок, а затем фильтрация дубликатовможет быть очень расточительным даже для немного больших значений n.Существуют более разумные способы создания только уникальных перестановок, которые можно использовать вместо itertools.permutations, см., Например, здесь или здесь .