How to make a grid of pairs of objects in linear time

Hello. I have an array [A, B, C, D, E] . How to make an array [[A, A], [A, B], [A, C], [A, D], [B, A], [B, B], [B, C]... ] in linear time? That is, I need pairs where each object interacts with each other.

What exactly do you mean by “linear time” here? Usually big-O notation uses n to refer to the size of the input, which for an array would be its count.

However, for an input array of count n, the output you appear to want is an array of count n2. Even if no work needs to be done, simply writing that output array to memory takes n2 steps, because it contains n2 elements.

• • •

On the other hand, if you are not tied to having an array specifically, it would be easy enough to make a specialized collection type which simply wraps the original collection and vends a subscript for the pairs.

If you allow the subscript to take a pair of the original collection’s indices, then it is trivial to make that work in constant time. If you insist on a “flattened” integer index, then the base collection would need to be random-access to achieve constant-time indexing.

Conversely, if you don’t need the result to be a collection, but would be satisfied with a sequence, then the base collection can simply be a collection.

I think product(_:_:) is what you're after.


Thanks. I am making a grid thread buffer to pass it on GPU 60 times per second.

Interesting idea, thanks.

Next time please do not abandon your post and ask a moderator to move it to the appropriate corner. ;)

Also shouldn‘t this go into #swift-users?