如何在给定索引的情况下生成特定的笛卡尔积

Question

我的问题

我正在尝试从一个非常大的笛卡尔积中生成一小部分可能的组合。我的输入将是一个数组数组，但每个数组的大小是动态的。目前，我使用的是 Python，但我对任何需要使用的语言持开放态度。

我的目标

看到这个问题后：How to select specific item from cartesian product without calculating every other item，我认为这是一个神奇的算法，可以给定一个索引生成一个集合。但是，这仅适用于 3 个阵列。我的最终目标是这样的，其中确定集合的函数是 find_set:

Input:
A = [ A_0, A_1, A_2, ..., A_n ]
B = [ B_0, B_1, B_2, ..., B_n ]
C = [ C_0, C_1, C_2, ..., C_n ]
D = [ D_0, D_1, D_2, ..., D_n ]
...
N = [ N_0, N_1, D_2, ..., N_n ]

List = [ A, B, C, D, ... N]

find_set(List, 0) -> [ A_0, B_0, C_0, ..., N_0 ]
find_set(List, 1) -> [ A_0, B_0, C_0, ..., N_1 ]
...

对于任何给定的索引，依此类推。

到目前为止我做了什么

我使用 Python 2.7 和 itertools.product 来生成所有的组合，但这只是一个迭代器。在运行进入内存消耗问题后，我尝试了这样的事情：

results = itertools.product(*List)

# generates 100,000 random indices between 0 and the size of the Cartesian Product
desired_indices = random.sample(xrange(0, calculated_size - 1), 100000) 

for item, index in results:
    if index in desired_indices:
          # do things

问题是，这无论如何都会导致 O(N) 次操作，当我有 433,501,216 个可能的集合时，这将花费很长时间才能找到一个非常小的子集。感谢所有帮助和任何其他资源，我可以寻求更多有关该主题的知识。

Answer 1

我不会说 Python，但我为 Scala 写了一个迭代器，它不需要存储中间结果，只需要一个索引。

如果您需要有关语法的更多信息，请告诉我。

基本思路如下：如果你有两个列表，一个是3，另一个是两个元素，(a,b,c) 和(1,2)，你可以生成(a1, a2, then b1、b2，最后是 c1、c2）。它完全由每个列表的长度控制，因此必须可以提前计算笛卡尔积的大小（2*3）或一般情况下的长度乘积，并通过对每个长度取模正确的顺序，对于 (0..size-1) 中的每个数字返回它的一组不同的元素。

class CartesianIterator [T] (val ll: Seq[Seq[T]]) extends Iterator [Seq[T]] { // with IndexedSeq [Seq[T]] {
  var current = 0L
  override val size = ll.map (_.size).product

  def get (n: Long): List[T] = {

      def get (n: Long, lili: Seq[Seq[T]]): List[T] = lili.length match {
        case 0L => List ()
        case _ => {
          val inner = lili.head
          inner ((n % inner.size).toInt) :: get (n / inner.size, lili.tail)
        }
      }

      get (n, ll)
  }

  override def hasNext () : Boolean = current != size
  override def next (): Seq[T] = {
    current += 1
    get (current - 1)
  }

    // IndexedSeq: Selects an element by its index in the sequence.
    // val x = CartesianIterator (...)
    // val res = x(123) // = x.apply (123)
    def apply (idx: Long): Seq[T] = {
        current = idx-1L
        next ()
    }
}

def exhaustiveDemo () {
  val ci = new CartesianIterator (List(List ('a', 'b'), List (1, 2, 3, 4), List ("foo", "bar", "baz")))
  for (p <-ci) println (p)
}

def massiveDemo () {
    val r = util.Random
    // 8 bit per value, ...
    val li = (0 to 256).toList
    // 256^8 combinations, 0 to Long.MaxValue
    val ll = List (li, li, li, li, li, li, li, li)
    val ci = new CartesianIterator (ll)
    for (i <- 0 to 9;
        rnd = math.abs(r.nextLong ());
        tuple = ci.get (rnd)
    ) println (tuple.mkString (":") + " at idx: " + rnd)
}

exhaustiveDemo ()
massiveDemo ()

示例输出：

List(a, 1, foo)
List(b, 1, foo)
List(a, 2, foo)
//...
List(b, 3, baz)
List(a, 4, baz)
List(b, 4, baz)

92:167:65:79:242:74:167:67 at idx: 5009630557992325817
252:176:16:94:68:30:43:44 at idx: 3270674835001624787
113:63:109:2:2:184:2:82 at idx: 6072977656466246445
95:68:232:237:171:233:183:114 at idx: 8494823201479688501
181:241:90:213:40:128:134:57 at idx: 4259670111450561340
29:113:165:134:150:89:247:72 at idx: 5402953717167499239
87:30:93:211:245:210:1:83 at idx: 6146770892844404160
25:205:116:230:196:105:62:37 at idx: 2757875964952116944
194:68:71:160:63:57:204:41 at idx: 3094941632910767450
166:133:37:249:17:6:215:92 at idx: 6874662895836376467

Answer 2

其实我是自己想出来的。万一其他人遇到这个，这里是 Python:

中的一个实现

import math

class LazyCartesianProduct:
    def __init__(self, sets):
        self.sets = sets
        self.divs = []
        self.mods = []
        self.maxSize = 1
        self.precompute()

    def precompute(self):
        for i in self.sets:
            self.maxSize = self.maxSize * len(i)
        length = len(self.sets)
        factor = 1
        for i in range((length - 1), -1, -1):
            items = len(self.sets[i])
            self.divs.insert(0, factor)
            self.mods.insert(0, items)
            factor = factor * items

    def entryAt(self, n):
        length = len(self.sets)
        if n < 0 or n >= self.maxSize:
            raise IndexError
        combination = []
        for i in range(0, length):
            combination.append(self.sets[i][ int(math.floor(n / self.divs[i])) % self.mods[i]])
        return combination

这实现了来自该网站的算法：http://phrogz.net/lazy-cartesian-product

如何在给定索引的情况下生成特定的笛卡尔积

How to generate a specific Cartesian Product given an index

python

set

cartesian-product

itertools