18

私はこの問題に対する答えがあるとほとんど確信していますが、私の一生の間、それを行う方法を理解することはできません。

私が3つのセットを持っているとしましょう：

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

そして、デカルト/クロス積を計算する方法を知っているので（このサイトや他の場所で、あちこちでカバーされています）、ここではそれについては説明しません。

私が探しているのは、セット全体を生成したり、n番目のアイテムに到達するまで反復したりせずに、デカルト積から特定のアイテムを簡単に選択できるアルゴリズムです。

もちろん、このような小さなサンプルセットを簡単に繰り返すことはできますが、私が取り組んでいるコードは、はるかに大きなセットで機能します。

したがって、私は関数を探しています。それを「CP」と呼びましょう。ここで、

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）時間で生成されます。

私は、必要なA、B、Cから要素のインデックスを計算し、元の配列からそれらを返すことが可能であるはずだという考えに従ってきましたが、私の試みはこれを正しく機能させるには、これまでのところ、機能していません。

私はPerlでコーディングしていますが、Python、JavaScript、またはJava（およびおそらく他のいくつか）からソリューションを簡単に移植できます。

4

3 に答える 3

29

可能な組み合わせの数は次の式で与えられます

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

から（排他的）までのi範囲のインデックスですべてのアイテムにインデックスを付けることができます。0N

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シフトすることができます。

于 2012-03-30T14:32:07.553 に答える
0

私はハワードによる答えのPythonバージョンを作成しました。改善できると思われる場合はお知らせください。

def ith_item_of_cartesian_product(*args, repeat=1, i=0):
    pools = [tuple(pool) for pool in args] * repeat   
    len_product = len(pools[0])
    for j in range(1,len(pools)):
        len_product = len_product * len(pools[j])
    if n >= len_product:
        raise Exception("n is bigger than the length of the product")
    i_list = []
    for j in range(0, len(pools)):
        ith_pool_index = i
        denom = 1
        for k in range(j+1, len(pools)):
            denom = denom * len(pools[k])
        ith_pool_index = ith_pool_index//denom
        if j != 0:
            ith_pool_index = ith_pool_index % len(pools[j])
        i_list.append(ith_pool_index)
    ith_item = []
    for i in range(0, len(pools)):
        ith_item.append(pools[i][i_list[i]])
    return ith_item
于 2019-06-12T19:40:45.843 に答える
0

ハワードの答えに基づいた短いPythonコードは次のとおりです。

import functools
import operator
import itertools

def nth_product(n, *iterables):
    sizes = [len(iterable) for iterable in iterables]
    indices = [
        int((n/functools.reduce(operator.mul, sizes[i+1:], 1)) % sizes[i])
        for i in range(len(sizes))]
    return tuple(iterables[i][idx] for i, idx in enumerate(indices))
于 2021-01-20T09:41:03.333 に答える