Генерация списка повторений независимо от порядка

Я хочу генерировать комбинации, которые связывают индексы в списке с "слотами". Например, (0, 0, 1) означает, что 0 и 1 принадлежат одному слоту, а 2-другому. (0, 1, 1, 1) означает, что 1, 2, 3 принадлежат одному и тому же слоту, а 0-само по себе. В этом примере 0 и 1 являются просто способами идентификации этих слотов, но не несут информации для моего использования.

Следовательно, (0, 0, 0) для моих целей абсолютно тождественно (1, 1, 1), а (0, 0, 1) эквивалентно (1, 1, 0).

В классическое декартово произведение порождает множество таких повторов, от которых я хотел бы избавиться.

Вот что я получаю с помощью itertools.product: 

>>> LEN, SIZE = (3,1)
>>> list(itertools.product(range(SIZE+1), repeat=LEN))
>>>
[(0, 0, 0),
(0, 0, 1),
(0, 1, 0),
(0, 1, 1),
(1, 0, 0),
(1, 0, 1),
(1, 1, 0),
(1, 1, 1)]

И вот что я хотел бы получить: 

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

Это легко с небольшими списками, но я не совсем понимаю, как это сделать с большими наборами. У вас есть предложение?

Если это неясно, пожалуйста, скажите мне, чтобы я мог прояснить свой вопрос. Спасибо!

Редактировать: исходя из ответа Sneftel, эта функция, кажется, работает, но я не знаю, действительно ли это дает все результаты: 

def test():
    for p in product(range(2), repeat=3):
        j=-1
        good = True
        for k in p:
            if k> j and (k-j) > 1:
                good = False
            elif k >j:
                j = k
        if good:
            yield p
4 5
python algorithm permutation combinatorics

4 ответа:

Я бы начал со следующих замечаний:

    Первый элемент каждой комбинации должен быть равен 0.
  1. второй элемент должен быть равен 0 или 1.
    2. Третий элемент должен быть 0, 1 или 2, но он может быть только 2, если второй элемент был 1.

Эти наблюдения предполагают следующий алгоритм: 

def assignments(n, m, used=0):
    """Generate assignments of `n` items to `m` indistinguishable
    buckets, where `used` buckets have been used so far.

        >>> list(assignments(3, 1))
        [(0, 0, 0)]
        >>> list(assignments(3, 2))
        [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1)]
        >>> list(assignments(3, 3))
        [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (0, 1, 2)]

    """
    if n == 0:
        yield ()
        return
    aa = list(assignments(n - 1, m, used))
    for first in range(used):
        for a in aa:
            yield (first,) + a
    if used < m:
        for a in assignments(n - 1, m, used + 1):
            yield (used,) + a

Это обрабатывает ваш случай использования (12 элементов, 5 ведер) в течение нескольких секунд: 

>>> from timeit import timeit
>>> timeit(lambda:list(assignments(12, 5)), number=1)
4.513746023178101
>>> sum(1 for _ in assignments(12, 5))
2079475

Это существенно быстрее, чем функция вы даете в конце вашего ответа (тот, который вызывает product и затем отбрасывает недопустимые назначения), было бы, если бы он был изменен для обработки (12, 5) прецедента использования: 

>>> timeit(lambda:list(test(12, 5)), number=1)
540.693009853363
2

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

Примерным результатом будет 

(0,0,0) -> (0,0,0)
(0,1,0) -> (0,1,0)

Но 

(1,0,1) -> (0,1,0)

Удаление дубликатов затем может быть легко выполнено, поскольку проблема сводится к проблеме решенный вопрос на Python: как удалить дубликаты списков в списке списка?

1

Если вы рассматриваете только элементы декартова произведения, где первые вхождения всех индексов отсортированы и последовательны от нуля, этого должно быть достаточно. itertools.combinations_with_replacement() исключит те, которые не отсортированы, поэтому вам нужно будет только проверить, что индексы не пропущены.

1

В вашем конкретном случае вы можете просто взять первую или вторую половину списка тех элементов, которые производятся декартовым продуктом. 

import itertools

alphabet = '01' 
words3Lettered = [''.join(letter) for letter in itertools.product(alphabet,repeat=3)]

Для n буквенных слов используйте repeat=n

Words3Lettered выглядит так: 

['000', '001', '010', '011', '100', '101', '110', '111']

Далее, 

usefulWords = words3Lettered[:len(words3Lettered)/2]

Который выглядит так: 

['000', '001', '010', '011']

ВАС МОЖЕТ ЗАИНТЕРЕСОВАТЬ другая половина, то есть words3Lettered[len(words3Lettered)/2:], хотя другая половина должна была "складываться" на первую половину.

Скорее всего, вы хотите использовать комбинацию Буквы в числовом виде так...

indexes = [tuple(int(j) for j in word) for word in usefulWords]

Что дает нам: 

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