创建笛卡尔积的最快方法，对内没有重复元素

Question

我有图像索引列表，它的长度是 60000。我想创建另一个包含随机索引对的列表。这里的约束是产品集的每个元素都应该包含不同的索引。换句话说，我不想自己将索引与它配对。

目前我一直在使用 itertools.product 方法和 for 循环。

pairs = []
for pair in itertools.product(indexes, indexes):
    if pair[0]!=pair[1]:
        pairs.append(pair)

问题是它花了很多时间，而且我无法使用我的电脑，因为它卡住了。

有更好的方法吗？

Answer 1

你可以懒惰地做而不存储它们:

pairs = filter(lambda x: x[0] != x[1], itertools.product(indexes, indexes))

如果使用 python2

，则使用 itertools.ifilter

使用 itertools 的想法是您不需要预先计算所有内容，而是要求一次计算一项（计算）。

我根据@Deepak Saini 做了一个时间比较，即live here:

import numpy as np
import itertools

indexes = np.arange(1000)

def pairs(indexes):
  pairs = []
  for pair in itertools.product(indexes, indexes):
      if pair[0]!=pair[1]:
          pairs.append(pair)
  return pairs

def iter_pairs(indexes):
  return filter(lambda x: x[0] != x[1], itertools.product(indexes, indexes))

def iter_pairs_no_lambda(indexes):
  def comp(x):
    return x[0] != x[1]
  return filter(comp, itertools.product(indexes, indexes))

import time
for f in (pairs, iter_pairs, iter_pairs_no_lambda):
  print(f.__name__)
  t1 = time.time()
  res = f(indexes)
  print("Took {}".format(time.time() -  t1))

结果：

pairs
Took 1.012538194656372
iter_pairs
Took 0.04567384719848633
iter_pairs_no_lambda
Took 0.0002455711364746094

Answer 2

import numpy as np

a = np.asarray(indexes)
b = np.copy(a)

while np.any(a == b):
    b = np.random.choice(a, size=a.shape[0], replace=False)

而且应该很快

创建笛卡尔积的最快方法，对内没有重复元素

fastest way to create cartesian product without duplicate elements inside pair

python

list

cartesian-product