I have all pair combinations from some list:
a = [1,2,3,4,5,6]
pairs = [pair for pair in itertools.combinations(a,2)]
print pairs
>>>[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]
How can I know what exactly pair I work with if I know only its index? Maybe there is some formula? The problem is that my list is too big and I can't just keep in mind all pairs. I need only some particular pairs which I can recognise by index.
Any suggestions?
Thanks!
Here's a way to generate a pair directly from its index. There's probably a more efficient equation for this, but this is what I came up with after a couple of minutes. :)
import itertools
def pair_from_index(a, i):
m = n = len(a) - 1
while i >= n:
i -= n
n -= 1
m -= n
return a[m], a[m + i + 1]
# test
a = list('abcdefg')
for i, t in enumerate(itertools.combinations(a, 2)):
print(i, t, pair_from_index(a, i))
output
0 ('a', 'b') ('a', 'b')
1 ('a', 'c') ('a', 'c')
2 ('a', 'd') ('a', 'd')
3 ('a', 'e') ('a', 'e')
4 ('a', 'f') ('a', 'f')
5 ('a', 'g') ('a', 'g')
6 ('b', 'c') ('b', 'c')
7 ('b', 'd') ('b', 'd')
8 ('b', 'e') ('b', 'e')
9 ('b', 'f') ('b', 'f')
10 ('b', 'g') ('b', 'g')
11 ('c', 'd') ('c', 'd')
12 ('c', 'e') ('c', 'e')
13 ('c', 'f') ('c', 'f')
14 ('c', 'g') ('c', 'g')
15 ('d', 'e') ('d', 'e')
16 ('d', 'f') ('d', 'f')
17 ('d', 'g') ('d', 'g')
18 ('e', 'f') ('e', 'f')
19 ('e', 'g') ('e', 'g')
20 ('f', 'g') ('f', 'g')
Here's an improved version that's about 10 times faster than the previous one on lists of length 500, and it should be even more efficient on larger lists.
def pair_from_index(a, i):
n = len(a) - 1
m = n * (n + 1) // 2
y = m - i - 1
d = 1 + int(((8*y + 1) ** 0.5 - 1) / 2)
k = n - d
return a[k], a[1 + i + k + d * (d + 1) // 2 - m]
I won't try to explain completely how it works, but it uses triangular numbers.
Let T(x) be the x'th triangular number, i.e., the sum of the numbers from 1 to x. The formula for T(x) is simple:
T(x) = x * (x + 1) / 2
Given y = T(x) we can calculate x by inverting the above formula
x = (8*y + 1) ** 0.5 - 1) / 2
Find a pair given an index:
my_pair = pairs[index]
Find an index* given a pair:
index = pairs.index(my_pair)
*Will give the index of the first instance of my_pair if more than one instance is in the list.
So... itertools.combinations gives you an iterator (see this):
>>> import itertools
>>> a = [1,2,3,4,5,6]
>>> itertools.combinations(a,2)
<itertools.combinations object at 0x10ca841d8>
Which means that it doesn't put all the possible items in memory until the item itself is requested.
One quick an dirty solution would be only keeping the items that you want. For instance, if you only want to keep pairs whose last item (or pair[1]) is equal to 4, you could do:
>>> pairs = [ pair for pair in itertools.combinations(a,2) if pair[1] == 4 ]
>>> pairs
[(1, 4), (2, 4), (3, 4)]
(assuming that pair[1] is what you call index)
If that's still too big, you might need to implement your own iterator, so you don't pre-load all the items in memory, but rather you calculate them only when requested.
If what you call index is the first item of the pair, you could use this in a similar fashion. For instance, let's say you only want items in which the first item (pair[0]) is equal to 2:
>>> pairs = [ pair for pair in itertools.combinations(a,2) if pair[0] == 2 ]
>>> pairs
[(2, 3), (2, 4), (2, 5), (2, 6)]
That would work... But if this is the case, is probably better if you use itertools.product, like this:
>>> [a for a in itertools.product([2], [5, 6, 7])]
[(2, 5), (2, 6), (2, 7)]
Or use map to apply a function to each item in the iterable...
>>> [a for a in map(lambda x: (2, x), [1, 2, 3])]
[(2, 1), (2, 2), (2, 3)]
If you have an index and you want to know the value, just get it with pairs[index]
pairs[ind][0]or some other detail? i.e. will you Not Know the contents of thepairbeforehand?I need only some particular pairs which I can recognise by index.You could get the combinations ofenumerate(a)which would include the indexing in that data if you mean the index ofa