# evan_tech

01:51 pm, 8 Jan 05

### a cs problem for y'all

So I've downloaded a bunch of this LJ friends data. For each user, I have a list of the other users they're linked to. Internally on LJ, these users are attached to numeric user ids, but these ids are not exposed in the data. It'd be nice to have the user ids because they correlate with the time someone joined LJ and that'd be interesting to study, but it would seem I'm out of luck. BUT, it turns out there is bit of information: these lists of users are sorted in order of user ids.

So the question: given a set of user lists, each of which contains a list of users ordered by userid, write an algorithm that tells me the overall ordering of these users. (I can't get back the actual user ids, of course, because there are potentially users I have no data for. And it's possible there are multiple solutions for a given input; I just need one.)

(PS: email me if you want the answer.)

•  Any constraints on memory usage? :-)Because it seems easy if not. reply to this
•  Hm... I guess you can assume enough memory to hold all of the user lists in memory simultaneously as well as some bookkeeping data. reply to this
•  I was going to ask you about multiple lists and islands of users, but you never found the islands if you did a recursive fdata fetch. reply to this
•  search.cpan.org for "partial order" gives Math-PartialOrder-0.01. Only 0.01 and from 2001, but looks fairly good. reply to this
•  Not at all efficient, but I'm in a rush because is coming over to hang out:```#!/usr/bin/python userlists = (('a', 'c', 'e'), ('b', 'c'), ('a', 'b'), ('e', 'f'), ('c', 'd', 'e')) pred = {} ordered = [] for userlist in userlists: prev_user = None for user in userlist: if not pred.has_key(user): pred[user] = [] if prev_user and (prev_user not in pred[user]): pred[user].append(prev_user) prev_user = user while 1: found = 0 for user in pred.keys(): if len(pred[user]) == 0: found = 1 ordered.append(user) del pred[user] for follow_user in pred.keys(): if user in pred[follow_user]: pred[follow_user].remove(user) if not pred: break if not found: raise RuntimeError, 'inconsistent user lists' print ordered``` reply to this
•  The second big while should just loop on pred instead of 1, but I've become conditioned to always loop on 1 and break inside of the loop, since I can't use assignments as conditions in Python. :( reply to this
•  are these continuous lists or non continuous.i.e: are they complete chunks from an overall list (i.e overlapping segments) ?or are they subsets of the data, where "a,c,..." means there could be an item between a and c ? reply to this
•  I'd imagine, given the way that these have to be retrieved, that there is no guarantee of a definitive answer as Evan said. All that we know is that all of these users are part of a graph, because they were fetched recursively. There will be no detatched nodes, but there will be a few cases where there isn't enough data to draw a conclusion about ordering. (users with only one friend) This sounds like a fun problem, but I've consumed too much alcohol to think about it now. reply to this