Random access over all pair-wise combinations of large list in Python

Question

Background:

I have a list of 44906 items: large = [1, 60, 17, ...]. I also have a personal computer with limited memory (8GB), running Ubuntu 14.04.4 LTS.

The Goal:

I need to find all the pair-wise combinations of large in a memory-efficient manner, without filling a list with all the combinations beforehand.

The Problem & What I've Tried So Far:

When I use itertools.combinations(large, 2), and try to assign it to a list my memory fills up immediately, and I get very slow performance. The reason for this is that the number of pairwise combinations goes like n*(n-1)/2 where n is the number of elements of the list.

The number of combinations for n=44906 comes out to 44906*44905/2 = 1008251965. A list with this many entries is much too large to store in memory. I would like to be able to design a function so that I can plug in a number i to find the ith pair-wise combination of numbers in this list, and a way to somehow dynamically compute this combination, without referring to a 1008251965 element list that's impossible to store in memory.

An Example of What I Am Trying To Do:

Let's say I have an array small = [1,2,3,4,5]

In the configuration in which I have the code, itertools.combinations(small, 2) will return a list of tuples as such:

[(1, 2), # 1st entry
 (1, 3), # 2nd entry
 (1, 4), # 3rd entry
 (1, 5), # 4th entry
 (2, 3), # 5th entry
 (2, 4), # 6th entry 
 (2, 5), # 7th entry
 (3, 4), # 8th entry
 (3, 5), # 9th entry
 (4, 5)] # 10th entry

A call to a the function like this: `find_pair(10)' would return:

(4, 5)

, giving the 10th entry in the would-be array, but without calculating the entire combinatorial explosion beforehand.

The thing is, I need to be able to drop in to the middle of the combinations, not starting from the beginning every time, which is what it seems like an iterator does:

>>> from itertools import combinations
>>> it = combinations([1, 2, 3, 4, 5], 2)
>>> next(it)
(1, 2)
>>> next(it)
(1, 3)
>>> next(it)
(1, 4)
>>> next(it)
(1, 5)

So, instead of having to execute next() 10 times to get to the 10th combination, I would like to be able to retrieve the tuple returned by the 10th iteration with one call.

The Question

Are there any other combinatorial functions that behave this way designed to deal with huge data sets? If not, is there a good way to implement a memory-saving algorithm that behaves this way?

Answer 1

Except itertools.combinations does not return a list - it returns an iterator. Here:

>>> from itertools import combinations
>>> it = combinations([1, 2, 3, 4, 5], 2)
>>> next(it)
(1, 2)
>>> next(it)
(1, 3)
>>> next(it)
(1, 4)
>>> next(it)
(1, 5)
>>> next(it)
(2, 3)
>>> next(it)
(2, 4)

and so on. It's extremely memory-efficient: only one pair is produced per invocation.

Of course it is possible to write a function that returns the n'th result, but before bothering with that (which will be slower and more involved), are you quite sure you can't just use combinations() the way it was designed to be used (i.e., iterating over it, instead of forcing it to produce a giant list)?