使用键从不同的列表中选择唯一的实体组合

Question

很抱歉，如果有人问了这个问题，我可能没有必要的词汇来找到正确的问题。

如果我有一些相同长度的列表(或多个元组)，如下所示：

[6, 4, 7] [gold, blue, red] [dog, cat, echidna] [hot, cold, rainy]

以及一组键，它们是已知范围内的连续整数，等于唯一组合的数目(在本例中为81)。

是否可以从每个列表中为每个键选择一项，以便保证组合是唯一的？(并从组合中获取密钥)。

所以

0可能会屈服(6，黄金，猫，热)

1可产(猫，4，金，雨)

2可能会屈服(热，红，灵，7)

等等。

并知道(热，红，针，7)的选择是由2？

假设列表的长度和顺序是已知和固定的，则保证列表中的项在每个列表中和在所有列表之间是唯一的，并且每个列表都可以被排序/排序。

Answer 1

您可以在不使用公式实现数据结构的情况下构建有效的映射。假设我们重复取n个序列的长度除以长度。这使我们：

def get_nth(seqs, n):
    out = []
    for seq in seqs:
        i = n % len(seq)
        n //= len(seq)
        out.append(seq[i])
    return out

之后我们就有了

>>> seqs = [[6, 4, 7], ['gold', 'blue', 'red'],
        ['dog', 'cat', 'echidna'], ['hot', 'cold', 'rainy']]
>>> get_nth(seqs, 0)
[6, 'gold', 'dog', 'hot']
>>> get_nth(seqs, 1)
[4, 'gold', 'dog', 'hot']
>>> get_nth(seqs, 80)
[7, 'red', 'echidna', 'rainy']
>>> len(set(tuple(get_nth(seqs, i)) for i in range(81)))
81

即使在很长的列表上，这也会很快起作用：

>>> seqs = [list(range(10**3))]*10**3
>>> %timeit get_nth(seqs, 0)
1000 loops, best of 3: 592 µs per loop
>>> %timeit get_nth(seqs, (10**3)**(10**3)-1)
100 loops, best of 3: 11.2 ms per loop
>>> get_nth(seqs, (10**3)**(10**3)-1)[:10]
[999, 999, 999, 999, 999, 999, 999, 999, 999, 999]

Answer 2

所有列表中的所有元素都是唯一的。

如果输入值在不同的列表中都是唯一的，那么您可以只。减少输出的元素

import itertools

input = [[6, 4], ['gold', 'blue'], ['dog', 'cat'], ['hot', 'cold']];
output = list(itertools.product(*input))
print output

所以list[0] -> (6, 'gold', 'dog', 'hot')

输出

 [(6, 'gold', 'dog', 'hot'), (6, 'gold', 'dog', 'cold'), (6, 'gold', 'cat', 'hot'), (6, 'gold', 'cat', 'cold'), 
 (6, 'blue', 'dog', 'hot'), (6, 'blue', 'dog', 'cold'), (6, 'blue', 'cat', 'hot'), (6, 'blue', 'cat', 'cold'), 
 (4, 'gold', 'dog', 'hot'), (4, 'gold', 'dog', 'cold'), (4, 'gold', 'cat', 'hot'), (4, 'gold', 'cat', 'cold'), 
 (4, 'blue', 'dog', 'hot'), (4, 'blue', 'dog', 'cold'), (4, 'blue', 'cat', 'hot'), (4, 'blue', 'cat', 'cold')]

并非所有列表中的所有元素都是唯一的。

那就用itertools.groupby吧

import itertools

input = [[1, 2], [1, 2], [1, 2], [1, 2]];
output = [k for k,_ in list(itertools.groupby(itertools.product(*input)))]
print output

输出

[[1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 2], [1, 1, 1, 2], [1, 1, 2, 2], [1, 2, 2, 2], 
[1, 1, 1, 2], [1, 1, 2, 2], [1, 2, 2, 2], [1, 1, 2, 2], [1, 2, 2, 2], [2, 2, 2, 2]]   

性能

用你的例子--时间--使用number=1000

0.00650215148926 (without group by)
0.02952003479    (with group by)
0.0323181152344  (algorithm from @GarrettR)

Answer 3

像这样的东西可能管用。我以为你没有钥匙的清单。相反，它通过枚举列表的产品来动态生成键。

a,b,c,d = [6, 4, 7], ['gold', 'blue', 'red'], ['dog', 'cat', 'echidna'], ['hot', 'cold', 'rainy']
from itertools import product
forward = {}
backward = {}
for i,thing in enumerate(product(a,b,c,d)):
    forward[i] = thing
    backward[thing] = i

前向映射示例

77 -> (7, 'red', 'cat', 'rainy')
78 -> (7, 'red', 'echidna', 'hot')
79 -> (7, 'red', 'echidna', 'cold')