4 replies to this topic

[Tasche]

Hello gamedevs!

i'm pretty sure this has been asked a million times before, but i couldn't come up with search keywords (which you probably can tell by the awkward topic title)
following problem:

i have got a set M of arbitrary data values of the same type.
now i have some random algorithm which pairs them up and puts them into a list, obeying the rule that although a data value may appear in several pairs, the symmetric counterpart (e.g. for the pair values <A,B>, with A,B in M, this would be the pair <B,A>) should not. also, no pair should appear twice.

the elements have, needless to say, no intrinsic ordering relation (else you could sort the pair to have the smaller always first, and would only need to check for the this item when looking if it already exists).

the obvious approach would be to search the entire list first item for A, and check if the pairing with B exists, then search the list's first item for B, and check if the pairing with A exists. if not, add the pair.

i am aware that in programming, you can always define an ordering relation by interpreting the data as a stream of 0 and 1, and use the induced ordering, but it seems so weak a solution. this problem just 'feels' like it can be solved more elegantly. if an ordering were used, what would be the quickest way? the one i mentioned using a sorted list?

i also hope i haven't offended anyone (or perhaps even clouded the question and/or assumptions) by my horrible translation of german math lingo into english.

cheers,
tasche

Edited by Tasche, 04 February 2013 - 02:10 PM.

[ApochPiQ]

What language are you planning on implementing this in?

[swiftcoder]

i am aware that in programming, you can always define an ordering relation by interpreting the data as a stream of 0 and 1, and use the induced ordering, but it seems so weak a solution. this problem just 'feels' like it can be solved more elegantly.

It's purely an implementation artefact, though. I'm not sure elegance is really the correct criteria to apply.

if an ordering were used, what would be the quickest way? the one i mentioned using a sorted list?

I'd probably go for a hash map of pairs, and check whether the reverse pair was already there before inserting. A hash map saves quite a bit of time complexity versus a sorted list - the insert becomes O(1) versus O(log n), not to mention that you don't need to sort it in the first place.

(in C++ that'd be something like a std::unordered_set<std::pair<A, B>>)

[Yrjö P.]

You could store all pairs ordered by min(A,B) and with every pair store a boolean that tells whether the values of that pair are reversed. That way you would not have to search twice for a read or write operation. Some variant of balanced binary search tree, like a red-black tree would be fine for this. In C++ std::map is implemented like that.

[Tasche]

You could store all pairs ordered by min(A,B) and with every pair store a boolean that tells whether the values of that pair are reversed. That way you would not have to search twice for a read or write operation. Some variant of balanced binary search tree, like a red-black tree would be fine for this. In C++ std::map is implemented like that.

min() only works with an ordering relation. i basically used swiftcoder's solution, which uses a map Pair->Value (the hash function), then collapse the buckets into a list. seems to perform well, and i learned something (which, btw, is a key goal of this exercise). this solution is also nicely scalable with respect to the expected data (and its amount), since i get to choose the hash function. most of the time i have lots of elements in M, but only few pairs get generated. +1 for swiftcoder (not that he needs any rep )