Picking persons in a group algorithm
-
Hey guys! Recently I posted this question "Picking entities from a group[^]" on the codeproject. I was advised to move it to this forum because some of you clever ones may have a way to go. My problem is that I have a group of n people (in my example I said 8 but let's say a minimum of four). I want each person in the group to point to a different person in the group. This means no person can point to himself. Also if a person points to some person in the group, no other person in the group can point to the same person. So everyone in the group must point to a person, and everyone in the group is pointed at. I also want the process to be random. For now I've already done this by creating a generic list of 'allowed' persons, pick a random person from the list, remove that person from the list and so on. Now here comes the difficult part.. I also want to be able to configure impossible combinations. Like Person A cannot point to Person B and Person B cannot point to Person A. This makes the process way more difficult. I'd like to have the ability to test whether a certain configuration is possible and to only pick between these possible 'combination sets'. My solution now, is a trial on error method. I start a large loop and start to random picking just like above. I generate a list of possibilities and pick one of the possibilities. If the list of possibilities happens to be empty, that means I ran into an impossible 'combination set' and start the entire process again. If the picking fails a certain number of times, I assume the configuration is impossible. As you understand my solution for now isn't ideal, 'cause there's no way to check whether a configuration is possible and if my picking routine tells me the configuration is not possible you're not actually sure the config is not possible. I think I got my problem explained well as my English is fairly good but way from perfect. Hope you guys can point me in a good direction. Thanks! Eduard
.: I love it when a plan comes together :.
-
Hey guys! Recently I posted this question "Picking entities from a group[^]" on the codeproject. I was advised to move it to this forum because some of you clever ones may have a way to go. My problem is that I have a group of n people (in my example I said 8 but let's say a minimum of four). I want each person in the group to point to a different person in the group. This means no person can point to himself. Also if a person points to some person in the group, no other person in the group can point to the same person. So everyone in the group must point to a person, and everyone in the group is pointed at. I also want the process to be random. For now I've already done this by creating a generic list of 'allowed' persons, pick a random person from the list, remove that person from the list and so on. Now here comes the difficult part.. I also want to be able to configure impossible combinations. Like Person A cannot point to Person B and Person B cannot point to Person A. This makes the process way more difficult. I'd like to have the ability to test whether a certain configuration is possible and to only pick between these possible 'combination sets'. My solution now, is a trial on error method. I start a large loop and start to random picking just like above. I generate a list of possibilities and pick one of the possibilities. If the list of possibilities happens to be empty, that means I ran into an impossible 'combination set' and start the entire process again. If the picking fails a certain number of times, I assume the configuration is impossible. As you understand my solution for now isn't ideal, 'cause there's no way to check whether a configuration is possible and if my picking routine tells me the configuration is not possible you're not actually sure the config is not possible. I think I got my problem explained well as my English is fairly good but way from perfect. Hope you guys can point me in a good direction. Thanks! Eduard
.: I love it when a plan comes together :.
this sounds like something Dynamic Programming[^] was designed to help with.
-
Hey guys! Recently I posted this question "Picking entities from a group[^]" on the codeproject. I was advised to move it to this forum because some of you clever ones may have a way to go. My problem is that I have a group of n people (in my example I said 8 but let's say a minimum of four). I want each person in the group to point to a different person in the group. This means no person can point to himself. Also if a person points to some person in the group, no other person in the group can point to the same person. So everyone in the group must point to a person, and everyone in the group is pointed at. I also want the process to be random. For now I've already done this by creating a generic list of 'allowed' persons, pick a random person from the list, remove that person from the list and so on. Now here comes the difficult part.. I also want to be able to configure impossible combinations. Like Person A cannot point to Person B and Person B cannot point to Person A. This makes the process way more difficult. I'd like to have the ability to test whether a certain configuration is possible and to only pick between these possible 'combination sets'. My solution now, is a trial on error method. I start a large loop and start to random picking just like above. I generate a list of possibilities and pick one of the possibilities. If the list of possibilities happens to be empty, that means I ran into an impossible 'combination set' and start the entire process again. If the picking fails a certain number of times, I assume the configuration is impossible. As you understand my solution for now isn't ideal, 'cause there's no way to check whether a configuration is possible and if my picking routine tells me the configuration is not possible you're not actually sure the config is not possible. I think I got my problem explained well as my English is fairly good but way from perfect. Hope you guys can point me in a good direction. Thanks! Eduard
.: I love it when a plan comes together :.
This sounds like a type of directed[^] graph[^] with indegree and outdegree 1. It has similarities to the Hamiltonian path problem[^], except that you could have multiple disconnected paths within the same graph. Not sure if that helps at all, or just confuses the problem! Hopefully, it might give you somewhere to start looking. :)
"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer
-
Hey guys! Recently I posted this question "Picking entities from a group[^]" on the codeproject. I was advised to move it to this forum because some of you clever ones may have a way to go. My problem is that I have a group of n people (in my example I said 8 but let's say a minimum of four). I want each person in the group to point to a different person in the group. This means no person can point to himself. Also if a person points to some person in the group, no other person in the group can point to the same person. So everyone in the group must point to a person, and everyone in the group is pointed at. I also want the process to be random. For now I've already done this by creating a generic list of 'allowed' persons, pick a random person from the list, remove that person from the list and so on. Now here comes the difficult part.. I also want to be able to configure impossible combinations. Like Person A cannot point to Person B and Person B cannot point to Person A. This makes the process way more difficult. I'd like to have the ability to test whether a certain configuration is possible and to only pick between these possible 'combination sets'. My solution now, is a trial on error method. I start a large loop and start to random picking just like above. I generate a list of possibilities and pick one of the possibilities. If the list of possibilities happens to be empty, that means I ran into an impossible 'combination set' and start the entire process again. If the picking fails a certain number of times, I assume the configuration is impossible. As you understand my solution for now isn't ideal, 'cause there's no way to check whether a configuration is possible and if my picking routine tells me the configuration is not possible you're not actually sure the config is not possible. I think I got my problem explained well as my English is fairly good but way from perfect. Hope you guys can point me in a good direction. Thanks! Eduard
.: I love it when a plan comes together :.
Here's another way of thinking about this: You have an array of values. The index into the array is the zero-based number of the person doing the pointing, and the value is the zero-based index of the person being pointed at. This automatically satisfies the rule that each person can only point to one other person. You then only need to validate that nobody is pointing to themselves, nobody is pointing to a forbidden person, and there are no duplicates.
public struct ForbiddenConnection
{
private readonly int _source;
private readonly int[] _destination;private ForbiddenConnection(int source, int\[\] destination) { \_source = source; \_destination = destination; } public static ForbiddenConnection Create(int source, IEnumerable<int> destination) { return new ForbiddenConnection(source, SortedDistinct(destination).ToArray()); } public static ForbiddenConnection Create(int source, params int\[\] destination) { return Create(source, destination.AsEnumerable()); } private static IEnumerable<int> SortedDistinct(IEnumerable<int> source) { if (source == null) yield break; bool started = false; int lastItem = 0; foreach (int item in source.OrderBy(x => x)) { if (started && item == lastItem) continue; yield return item; lastItem = item; started = true; } } public int Source { get { return \_source; } } public bool Contains(int destination) { return \_destination != null && Array.BinarySearch(\_destination, destination) >= 0; }}
public sealed class GraphGenerator : IEnumerable<IReadOnlyList<int>>
{
private readonly int _length;
private readonly IDictionary<int, ForbiddenConnection> _forbidden;private GraphGenerator(int length, IEnumerable<ForbiddenConnection> forbidden) { \_length = length; if (forbidden != null) { \_forbidden = forbidden.ToDictionary(fc => fc.Source); } else { \_forbidden = new Dictionary<int, ForbiddenConnection>(0); } } public static GraphGenerator Create(int length, IEnumerable<ForbiddenConnection> forbidden) { if (length < 2) throw new Arg -
Here's another way of thinking about this: You have an array of values. The index into the array is the zero-based number of the person doing the pointing, and the value is the zero-based index of the person being pointed at. This automatically satisfies the rule that each person can only point to one other person. You then only need to validate that nobody is pointing to themselves, nobody is pointing to a forbidden person, and there are no duplicates.
public struct ForbiddenConnection
{
private readonly int _source;
private readonly int[] _destination;private ForbiddenConnection(int source, int\[\] destination) { \_source = source; \_destination = destination; } public static ForbiddenConnection Create(int source, IEnumerable<int> destination) { return new ForbiddenConnection(source, SortedDistinct(destination).ToArray()); } public static ForbiddenConnection Create(int source, params int\[\] destination) { return Create(source, destination.AsEnumerable()); } private static IEnumerable<int> SortedDistinct(IEnumerable<int> source) { if (source == null) yield break; bool started = false; int lastItem = 0; foreach (int item in source.OrderBy(x => x)) { if (started && item == lastItem) continue; yield return item; lastItem = item; started = true; } } public int Source { get { return \_source; } } public bool Contains(int destination) { return \_destination != null && Array.BinarySearch(\_destination, destination) >= 0; }}
public sealed class GraphGenerator : IEnumerable<IReadOnlyList<int>>
{
private readonly int _length;
private readonly IDictionary<int, ForbiddenConnection> _forbidden;private GraphGenerator(int length, IEnumerable<ForbiddenConnection> forbidden) { \_length = length; if (forbidden != null) { \_forbidden = forbidden.ToDictionary(fc => fc.Source); } else { \_forbidden = new Dictionary<int, ForbiddenConnection>(0); } } public static GraphGenerator Create(int length, IEnumerable<ForbiddenConnection> forbidden) { if (length < 2) throw new ArgUpvoted. What a fascinating answer ! I look forward to studying this code. thanks, Bill
Google CEO, Erich Schmidt: "I keep asking for a product called Serendipity. This product would have access to everything ever written or recorded, know everything the user ever worked on and saved to his or her personal hard drive, and know a whole lot about the user's tastes, friends and predilections." 2004, USA Today interview
