des.shulepov
BAN USERThanks for your input. I did not check if there are other possible solutions for 7, mainly because my backtrack algorithm starts by putting n at 0 and usually it either find the solution having n at 0 index, or does not find it at all. For n=3 and n=4 I could not find any more solutions. So,
2. For each valid n there are at least 2 solutions. One of which having n on position 0. All solutions are mirrored I.e. for 4: it's 4 1 3 1 2 4 3 2 and 2 3 4 2 1 3 1 4
3. For the solution, where n goes at 0, n-1 is at 2, for all observed n > 3 < 16.
I think the simplies solution for this is a dictionary of dictionaries. We need to quickly find relations for a given key (email), so dictionary with key by email. We might have selveral relations and we need to store weight for each of them, so another dictionary.
I've created a small sample in C#:
public class RelatedContacts
{
private readonly Dictionary<string, Dictionary<string, int>> _storage;
public RelatedContacts (IEnumerable<string> emailRecipients)
{
_storage = new Dictionary<string,Dictionary<string,int>>(StringComparer.InvariantCultureIgnoreCase);
foreach (var recipients in emailRecipients)
{
var emails = recipients.Split(new[] { ';', ',' }, StringSplitOptions.RemoveEmptyEntries);
if (emails.Length < 2) continue;
for (var i = 0; i < emails.Length; i++)
{
for (var j = i + 1; j < emails.Length; j++)
{
relate(_storage, emails[i].Trim(), emails[j].Trim());
relate(_storage, emails[j].Trim(), emails[i].Trim());
}
}
}
}
private static void relate(Dictionary<string, Dictionary<string, int>> relations, string emailA, string emailB)
{
Dictionary<string, int> contacts;
if (!relations.TryGetValue(emailA, out contacts)) contacts = new Dictionary<string, int>(StringComparer.InvariantCultureIgnoreCase);
int weight = 0;
contacts.TryGetValue(emailB, out weight);
contacts[emailB] = weight + 1;
relations[emailA] = contacts;
}
public IEnumerable<string> Get(string email)
{
Dictionary<string, int> contacts;
if (!_storage.TryGetValue(email, out contacts)) return Enumerable.Empty<string>();
return contacts.OrderBy((_) => _.Value).Select(_ => _.Key);
}
public IEnumerable<string> Get(IEnumerable<string> emails)
{
Dictionary<string, int> result = new Dictionary<string, int>();
Dictionary<string, int> contacts;
foreach (var email in emails)
{
if (!_storage.TryGetValue(email, out contacts)) continue;
foreach (var pair in contacts)
{
int weight = 0;
result.TryGetValue(pair.Key, out weight);
result[pair.Key] = weight + pair.Value;
}
}
return result.OrderBy((_) => _.Value).Select(_ => _.Key);
}
}
Ok, probably it's too much code in my solution without explanation.
- des.shulepov November 18, 2014So, it's a directed weighted graph, represented as sparse matrix where vertex is email and for each vertex we store a list of adjacent vertexes with weights.
Data may be persisted as 2 files or tables:
1. list of vertexes: (email, int key) pairs
2. one to many relation of int vertex key to pair of another vertex key and weight
Some improvements might be suggested to my initial solution:
1. If the total number of distinct emails is big it's better to create a help dictionary to associate email with int key and use it to represent vertex in a graph (i.e. dictionary in the code above). Because it's cheaper to store int than pointer to string.
2. If average number of related contacts is not big, we could use a list to store adjacent vertexes. This trade off will be slower on adding related contacts, but will consume less memory.
3. Initial solution is done as immutable class, but it's not hard to add method for adding relations.