如何选择从笛卡尔积特定项目不计算其他所有项目 [英] 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.

当然，我可以很容易地重复了一个小例子，这样设置，但code我的工作将与更大的集来工作。

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)

和你可以索引的所有项目由一个指数我从 0 到ñ （独家）通过

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)

（所有集合被认为是可转位出发王氏零， / 是整数除法）。

为了让您的例子中，你可以通过1移位指数。

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

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