Итерации по всем спискам с одним дубликатом

Question

Рассмотрите все списки длины n, где значения являются целыми числами от range 0 to n-1. Я хотел бы как можно быстрее повторить все возможные списки, которые имеют ровно один дубликат. Если n = 2 то возможные списки:

00 
11 

Если n = 3 они:

001 
002 
110 
112 
220 
221 
100 
200 
011 
211 
022 
122 
010 
020 
101 
121 
202 
212 

Общее количество таких списков n! * (n choose 2), поэтому я хотел бы избежать хранения их в памяти, если это вообще возможно ,

Для каждого списка я хочу вызвать функцию, которая вычисляет функцию из списка.
Каков хороший способ сделать это?

Бенчмарки На моем компьютере я получаю следующие результаты тестов

timeit all(one_duplicate(6)) 
100 loops, best of 3: 6.87 ms per loops 
timeit all(one_duplicate(7)) 
10 loops, best of 3: 59 ms per loop 
timeit all(one_duplicate(8)) 
1 loops, best of 3: 690 ms per loop 
timeit all(one_duplicate(9)) 
1 loops, best of 3: 7.58 s per loop 

и

timeit all(duplicates(range(6))) 
10 loops, best of 3: 22.8 ms per loop 
timeit all(duplicates(range(7))) 
1 loops, best of 3: 416 ms per loop  
timeit all(duplicates(range(8))) 
1 loops, best of 3: 9.78 s per loop 

и

timeit all(all_doublet_tuples(6)) 
100 loops, best of 3: 6.36 ms per loop 
timeit all(all_doublet_tuples(7)) 
10 loops, best of 3: 60 ms per loop 
timeit all(all_doublet_tuples(8)) 
1 loops, best of 3: 542 ms per loop 
timeit all(all_doublet_tuples(9)) 
1 loops, best of 3: 7.27 s per loop 

Я заявляю all_doublet_tuples и one_duplicate быть равны первым на данный момент (с учетом шума в тестах).

Answer 1

Придумайте любого желаемых выходных кортежей в этом случае : Это было получено путем дублирования первого (пусть говорят слева) дублета elem и ins удерживая его в положении второго дублета.

Поэтому мое решение в основном это два шага процесс:

1. порождает все n-1 перестановок range(n)
2. для каждого кортежа из 1 .:
   взять каждый отдельный элемент и вставить его в каждом положении впереди (во избежание дубликатов), в том числе в самом конце

---

import itertools as it 

# add_doublet accomplishes step 2 
def add_doublet(t): 
    for i in range(len(t)): 
     for j in range(i+1, len(t)+1): 
      yield t[:j] + (t[i],) + t[j:] 


def all_doublet_tuples(n): 
    for unique_tuple in it.permutations(range(n), n-1): 
     for doublet_tuple in add_doublet(unique_tuple): 
      yield doublet_tuple 



from pprint import pprint 

n = 3 
pprint(list(all_doublet_tuples(n))) 

Я не печатаю вывод здесь, потому что его вид длины ... и корпус для n = 3 является скучным.

Answer 2

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

Общее количество возможных списков - n * (n-1) * (n выбор 2), поэтому я хотел бы избежать их хранения в памяти, если это вообще возможно.

Вам просто нужно создать функцию генератора, yield сек ответил один за другим, вместо обычной функции, которая добавляет каждый ответ на list, а затем возвращает его list.

Для каждого списка я хочу вызвать функцию, которая вычисляет функцию списка. Каков хороший способ сделать это?

Вы можете вызвать функцию генератора и использовать результат как итератор. Например:

for element in my_generator_function(n): 
    my_function(element) 

Если вы хотите, чтобы результаты вызова my_function каждого элемента, вы можете создать еще одну функцию генератора:

def apply_to(my_function, my_iterator): 
    for element in my_iterator): 
     yield my_function(element) 

Однако уже есть встроенная функция, которая делает именно то, что, map в Python 3, или itertools.imap в Python 2.

Или, еще проще, вы можете использовать выражение генератора:

results = (my_function(element) for element in my_generator_function(n)) 

Более подробно см раздел Iterators, Generators и Generator Expressions в официальном учебнике Python.

Теперь вы можете разбить вашу проблему вниз, как это:

• Для каждого числа в множестве первых п чисел:
  • Все перестановки этого числа в два раза, вместе с п-2 остальные номера

при п = 2, это означает, что все перестановки (0, 0) вместе с номерами от 0 (1), и всех перестановок (1, 1) вместе с 0 количесом rs из (0). Для n = 3 у вас есть все перестановки (0, 0) вместе с 1 из чисел (1, 2) и все перестановки (1, 1) вместе с 1 из чисел (0, 2), и все перестановки (2, 2) вместе с 1 из чисел (0, 1). И так далее.

Таким образом, перевод, что непосредственно на Python, с помощью магии itertools:

def one_duplicate_element(n): 
    for i in range(n): 
     rest = (j for j in range(n) if j != i) 
     for combination in itertools.combinations(rest, n-2): 
      yield from itertools.permutations(combination + (i, i)) 

Это использует yield from заявления в Python 3.3, что означает «выход каждый элемент из этого итератора». Если вы используете 3.2 или выше, вы должны сделать это явно с петлей:

def one_duplicate_element(n): 
    for i in range(n): 
     rest = (j for j in range(n) if j != i) 
     for combination in itertools.combinations(rest, n-2): 
      for permutation in itertools.permutations(combination + (i, i)): 
       yield permutation 

Но вы заметите, что, в то время как это делает именно то, что вы просили, он не генерирует такой же список как ваш образец. Даже игнорируя порядок (который, как мне кажется, не подходит для вас), есть дубликаты. Зачем?

Ну, что такое перестановки в наборе (0, 0)? Это спорный вопрос; (0, 0) не может быть множеством, потому что в нем есть дубликаты. Итак, что бы ни было (0, 0), каковы его перестановки? Ну, по обычному определению перестановок на упорядоченных кортежах, что будет ((0, 0), (0, 0)). И это именно то, что дает вам itertools.permutations.

Вы можете посмотреть на то, как permutations работы и написать permutations_without_duplicates функции самостоятельно, или вы можете использовать функцию unique_everseen в Recipes разделе Документов, или вы можете сортировать результаты и использовать unique_justseen, или ... Ну, давайте выберем один:

def one_duplicate_element_no_duplicates(n): 
    yield from unique_everseen(one_duplicate_element(n)) 

Answer 3

import itertools 

def one_duplicate(n): 
    nrange = list(range(n)) 
    for x in nrange: 
     without_x = nrange[:x] + nrange[x+1:] 
     for i, j in itertools.combinations(nrange, 2): 
      for others in map(list, itertools.permutations(without_x, n-2)): 
       others.insert(i, x) 
       others.insert(j, x) 
       yield others 

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

Вот описание алгоритма:

• Найти индекс р транслируется с помощью itertools.combinations(nrange, 2)
• Для каждого номера x в диапазоне, получить все перестановки длины n-2 для всего диапазона, за исключением x
• В каждом из этих перестановок, вставьте x на каждый из индексов, найденных на первой стадии и выходе результат.

Зубчатые сравнения между моим ответом и Peter Stahl's:

# Just showing they both get the same result 
In [23]: set(peter(range(6))) == set(tuple(x) for x in fj(6)) 
Out[23]: True 

In [24]: %timeit list(peter(range(6))) 
10 loops, best of 3: 27.3 ms per loop 

In [25]: %timeit list(fj(6)) 
100 loops, best of 3: 8.32 ms per loop 

In [26]: %timeit list(peter(range(7))) 
1 loops, best of 3: 506 ms per loop 

In [27]: %timeit list(fj(7)) 
10 loops, best of 3: 81 ms per loop 

Answer 4

from itertools import product  

def duplicates(r): 
    r_len = len(r) 
    dup_len = r_len - 1 
    for tup in product(r, repeat=r_len): 
     if len(set(tup)) == dup_len: 
      yield tup 

>>> list(duplicates(range(2))) 
[(0, 0), (1, 1)] 

>>> list(duplicates(range(3))) 
[(0, 0, 1), 
(0, 0, 2), 
(0, 1, 0), 
(0, 1, 1), 
(0, 2, 0), 
(0, 2, 2), 
(1, 0, 0), 
(1, 0, 1), 
(1, 1, 0), 
(1, 1, 2), 
(1, 2, 1), 
(1, 2, 2), 
(2, 0, 0), 
(2, 0, 2), 
(2, 1, 1), 
(2, 1, 2), 
(2, 2, 0), 
(2, 2, 1)] 

несколько тестов на моей машине:

%timeit all(duplicates(range(5))) 
100 loops, best of 3: 2.5 ms per loop 

%timeit all(duplicates(range(6))) 
10 loops, best of 3: 38.6 ms per loop 

%timeit all(duplicates(range(7))) 
1 loops, best of 3: 766 ms per loop 

%timeit all(duplicates(range(8))) 
1 loops, best of 3: 18.8 s per loop 

Answer 5

import itertools 
n=3 
for i in range(n-1): 
    for j in range(n-i-1): 
     for perm in map(list, itertools.permutations(range(n), n-1)): 
      perm.insert(i, perm[i+j]) 
      print perm 

ключевой концепцией здесь, чтобы генерировать все N-1 длины перестановок из н-длины, а затем просто запустить его на все комбинации повторения (I и I + J)

В случае N = 3, перестановки:

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

и повторяющиеся элементы может быть в положениях, обозначенных символом X:

XX_, X_X, _xx

Ваши результаты, является 'умножение' из этих множеств:

 XX_ X_X _XX 
(0, 1) 001 010 011 
(0, 2) 002 020 022 
(1, 0) 110 101 100 
(1, 2) 112 121 122 
(2, 0) 220 202 200 
(2, 1) 221 212 211 

Все вычисляется на лету. Я думаю, что потребление памяти - O (N).