如何从笛卡尔积中选择特定项目而不计算所有其他项目 [英] How to select specific item from cartesian product without calculating every other item

问题描述

我深信这个问题是有答案的，但我终生不知道该怎么做.

I'm mostly convinced that there is an answer to this problem, but for the life of me can't figure out how to do it.

假设我有三组:

A = [ 'foo', 'bar', 'baz', 'bah' ]
B = [ 'wibble', 'wobble', 'weeble' ]
C = [ 'nip', 'nop' ]

而且我知道如何计算笛卡尔积/叉积，(在本网站和其他地方，到处都覆盖了它)所以我不会在这里讨论.

And I know how to calculate the cartesian / cross product, (ant it's covered all over the place, on this site and elsewhere) so I won't go over that here.

我正在寻找的是一种算法，它允许我简单地从笛卡尔积中选择一个特定的项目而不生成整个集合或迭代直到我到达第 n 个项目.

What I'm looking for is an algorithm that would allow me to simply select a specific item from the cartesian product without generating the whole set or iterating until I reach the nth item.

当然，我可以轻松地迭代这样一个小示例集，但我正在处理的代码将处理更大的集.

Of course, I could easily iterate for a small example set like this, but the code I am working on will be working with much larger sets.

因此，我正在寻找一个函数，我们称之为CP"，其中:

Therefore, I'm looking for a function, let's call it 'CP', where:

CP(1) == [ 'foo', 'wibble', 'nip' ]
CP(2) == [ 'foo', 'wibble', 'nop' ]
CP(3) == [ 'foo', 'wobble', 'nip' ]
CP(4) == [ 'foo', 'wobble', 'nop' ]
CP(5) == [ 'foo', 'weeble', 'nip' ]
CP(6) == [ 'foo', 'weeble', 'nop' ]
CP(7) == [ 'bar', 'wibble', 'nip' ]
...
CP(22) == [ 'bah', 'weeble', 'nop' ]
CP(23) == [ 'bah', 'wobble', 'nip' ]
CP(24) == [ 'bah', 'wobble', 'nop' ]

答案是在 O(1) 时间内产生的，或多或少.

And the answer is produced in O(1) time, more or less.

我一直认为应该有可能(哎呀，甚至很简单！)计算我想要的 A、B、C 中元素的索引，然后简单地从原始数组中返回它们，但到目前为止，我尝试使这项工作正常进行，嗯，没有奏效.

I've been following the idea that it should be possible, (heck, even simple!) to calculate the indices of the elements from A,B,C that I want and then simply return the them from the original arrays, but my attempts to make this work correctly have so far, um, not worked.

我使用 Perl 进行编码，但我可以轻松地从 Python、JavaScript 或 Java(可能还有其他一些)移植解决方案

I'm coding in Perl, but I can handily port a solution from Python, JavaScript, or Java (and probably a few others)

推荐答案

可能的组合数由

N = size(A) * size(B) * size(C)

并且您可以通过索引i索引所有项目，范围从0到N(独占)通过

and you can index all items by an index i ranging from 0 to N (exclusive) via

c(i) = [A[i_a], B[i_b], C[i_c]]

哪里

i_a = i/(size(B)*size(C)) 
i_b = (i/size(C)) mod size(B)
i_c = i mod size(C)

(假设所有集合都可以从零开始索引，/ 是整数除法).

(all sets are assumed to be indexable starting wih zero, / is integer division).

为了得到你的例子，你可以将索引移动 1.

In order to get your example you may shift the index by 1.

这篇关于如何从笛卡尔积中选择特定项目而不计算所有其他项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！