4

考虑所有长度列表，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_tuplesandone_duplicate是平等的（考虑到测试中的噪音）。

4

5 回答 5

5

以这种方式考虑任何所需的输出元组：它是通过复制第一个（让我们从左边开始）doublet elem 并将其插入到第二个 doublet 的位置而得出的。

因此我的解决方案基本上是这个两步过程：

  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 的情况很无聊。

于 2013-02-13T20:30:35.880 回答
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第一步中找到的每个索引并产生结果。

我的答案和彼得斯塔尔的答案之间的时间比较：

# 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
于 2013-02-13T19:51:17.547 回答
2 
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 长度集合中生成所有 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）。

于 2013-02-13T20:39:43.563 回答
1

您的问题是关于如何在不创建实际list内存的情况下这样做，以及如何在每个函数上运行一个函数，所以我将首先一般地回答该部分，然后针对您的具体问题。

可能列表的总数是 n*(n-1) * (n choose 2) 所以我想尽可能避免将它们全部存储在内存中。

您只需要创建一个生成器函数，它s 一个一个地回答，而不是一个将每个答案附加到 a然后返回yield的常规函数​​。listlist

对于每个列表，我想调用一个计算列表函数的函数。有什么好方法可以做到这一点？

您可以调用生成器函数并将结果用作迭代器。例如：

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.imapPython 2 中调用。

或者，更简单地说，您可以使用生成器表达式：

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

有关更多信息，请参阅官方 Python 教程中的迭代器、生成器和生成器表达式部分。

现在，您可以像这样分解您的问题：

  • 对于前 n 个数字的集合中的每个数字：
    • 该数字的所有排列两次，以及其他数字的 n-2

对于 n=2，这意味着 (0, 0) 的所有排列连同 (1) 中的 0 个数，以及 (1, 1) 的所有排列以及 (0) 中的 0 个数。对于 n=3，您得到 (0, 0) 的所有排列和数字 (1, 2) 中的 1 个，以及 (1, 1) 和数字 (0, 2) 中的 1 个的所有排列，以及 (2, 2) 的所有排列以及数字 (0, 1) 中的 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 fromPython 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函数，或者您可以对结果进行排序并使用, 或……好吧，让我们选择一个：unique_justseen

def one_duplicate_element_no_duplicates(n):
    yield from unique_everseen(one_duplicate_element(n))
于 2013-02-13T19:43:25.127 回答
1 
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
于 2013-02-13T19:57:43.187 回答