none
Comparing Number Sets - Get All Possible Combinations?

    Question

  • I am still stuck on this issue, I have asked on a few different forums, but no one seems to know the answer. I have been trying for nearly three weeks now every chance I get and I am so stuck and confused now, I don't even know what to lookup anymore. I tried searching Google many, many times but I am not even sure what I am looking for so its making it impossible.

    I need a program that will compare values, we can use numbers they will work fine. I have only a few requirements

    1. The static set must be used.
    2. I total number of numbers used must be equal to ten.
    3. No number can be used more then once.
    4. The sets cannot be taken apart, they are already calculated.

    I'm sure this is a simple comparison but I can't get it and I am so tired of this I just want to move on.

    If I gave you the following sets of numbers, and the rules above, how would you solve this?

    Static Set: {132 114 012}

    Set 1: {071 072 073}
    Set 2: {072 073 074}
    Set 3: {071 073 074}
    Set 4: {071 072 073 074}
    Set 5: {041 051 061}
    Set 6: {051 061 071}
    Set 7: {041 051 061 071}

    My idea was to try and loop through each set and compare them one by one, but in some cases, depending on the number sets this will take a unreasonable amount of iterations, and way too much CPU usage.

    But with my idea I would compare Set 1 to Set 2, and then Set 1 to Set 3, and then Set 1 to Set 4, etc...

    Then start over at Set 2. Since Set 2 was already compared with Set 1 in the previous loop, I compare Set 2 with Set 3, and Set 4, etc...

    If you compare Set 1 to Set 2 you can see its invalid because number 072 is used twice. It appears in Set 1 and Set 2.

    Anyway, I have done this in my head and the only two possible combinations are:

    Set 2: {072 073 074} & Set 7: {041 051 061 071} + Static {132 114 012}

    Or

    Set 1: {071 072 073 074} & Set 5: {041 051 061} + Static {132 114 012}

    You can see that in Set 2 and Set 7 no number is used twice, and in Set 1 and Set 5 also no number is used twice.

    Also when I add the static set to the end of both of those sets, the total number of numbers equals 10. In this case there are only two possible matches that are valid, but sometimes there are a lot of matches that could possibly work.

    In simple terms I want to compare each of the sets, throwing in the static set and see how many possible combinations can be made. I need to record all of the combinations beacuse they will be used in the next step.

    This is a four step process, I know how to do every step with code except step number 3, comparing these sets. I have found many articles on google about comparing numbers and strings, but nothing I could find about comparing sets of numbers, without duplicating the numbers, and also throwing in a static set of numbers.

    I'm really suck on this, so I hope someone here can see the pattern here and help me out, I know there has to be a pattern here but I can't see it.

    Can anyone help me get this started?
    Saturday, March 21, 2009 5:00 AM

All replies

  • Do you have a test case the would use an unreasonable amount of iterations and cpu power? My current solution takes 4-5ms with the set you posted.

    using System;  
    using System.Collections.Generic;  
    using System.Linq;  
    using System.Text;  
    using System.Diagnostics;  
     
    namespace ConsoleApplication11  
    {  
        class Program  
        {  
            static void Main(string[] args)  
            {  
                List<int> stat =  new List<int>() { 132,114,012 };  
                List<int> [] Sets = {  
                                        new List<int>() {071,072,073},  
                                        new List<int>() {072,073,074},  
                                        new List<int>() {071,073,074},  
                                        new List<int>() {071,072,073,074},  
                                        new List<int>() {041,051,061},  
                                        new List<int>() {051,061,071},  
                                        new List<int>() {041,051,061,071}  
                                    };  
                Stopwatch sw = new Stopwatch();  
                sw.Start();  
                FindSets(stat, Sets,0);  
                sw.Stop();  
                Console.WriteLine("Done in {0} ms",sw.ElapsedMilliseconds);  
            }  
     
            static bool IsCompatible(List<int> cur, List<int> test)  
            {  
                for (int i = 0; i < test.Count; i++)  
                {  
                    if (cur.Contains(test[i]))  
                        return false;  
                }  
                return true;  
            }  
     
            static int[] CompatibleSets(List<int> cur, List<int>[] Sets, int startIdx)  
            {  
                List<int> Res = new List<int>();  
                for (int i = startIdx; i < Sets.Length; i++)  
                {  
                    if (IsCompatible(cur,Sets[i]))  
                    {  
                        Res.Add(i);  
                    }  
                }  
                return Res.ToArray();  
            }  
            private static Stack<int> SelectedSets = new Stack<int>();  
     
            private static void FindSets(List<int> stat, List<int>[] Sets,int StartIDx)  
            {  
                if (stat.Count > 10)  
                    return;  
                  
                if (stat.Count == 10)  
                {  
                    Console.Write("Static ");  
                    foreach (int set in SelectedSets)  
                    {  
                        Console.Write(" + {0} ",set+1);  
                    }  
                    Console.Write(" : ");  
                    foreach (int val in stat)  
                        Console.Write(" {0} ", val);  
                    Console.WriteLine();  
                    return;  
                }  
     
                int[] pos = CompatibleSets(stat, Sets,StartIDx);  
                for (int i = 0; i < pos.Length; i++)  
                {  
                    List<int> NewSet = new List<int>();  
                    NewSet.AddRange(stat);  
                    NewSet.AddRange(Sets[pos[i]]);  
                    SelectedSets.Push(pos[i]);  
                    FindSets(NewSet, Sets, pos[i] + 1);  
                    SelectedSets.Pop();  
                }  
            }  
        }  
    }  
     


     What are you doing anyway?

    Saturday, March 21, 2009 7:13 AM
  • you question is bit confusing for me, what really you want to say.
    how ever what i understand is

    suppose you have 100 sets
    find distinct number in all sets, and create an array of it,
     
    suppose you obtain 20 distinct number,
    then using formula for comination "n!/(n-k)!"  = number of combination of size "k" in your case "10"

    then there are two cases of your problem
    1) then recursively create the sets, in which each set has distinct number, but sets are not disjoint, suppose set a = {1,2,3,4}
    b = {1,2,3,5}

    the following case matching to your problem
    2) in which each set will be disjiont (non overlap) then the solution is following 
    http://en.wikipedia.org/wiki/Disjoint-set_data_structure


    Seek Knowledge From Cradle to Grave
    Saturday, March 21, 2009 7:19 AM
  • I may be going about it the wrong way but I am trying to validate a Gin Rummy hand for my card game. It is very complex because of the requirements that Gin Rummy uses. I have been working on this for a long time (weeks) and its seriously annoying me at this point. So I was trying to do the validation by using a table that I designed.

    You can view the table here.

    The problem is that most people are not much help on the issue because they do not know how to play Gin Rummy. I received one possible solution from another website, but I have no idea how to implement it. I have been trying for some time and keep coming up short.

    I thought by creating that table and working with numbers for some reason it would make the process easier. But at this point I'm about giving up, as I've been working on this for weeks and I can't make any progress. It's about time to move on. I haven't had a chance to look at your solution yet, but I will test it and reply about it as soon as I can.

    Thanks!

    Response - Source
    [quote]
    I think there would be some application of these algorithms when validating hands, but since the end result desired is just a boolean, iterating through millions of options would not be highly desirable. So, I can think of two direct applications of these classes that would determine if a hand had all 10 cards melded, neither of which I would use. And finally one that I would think would be effecient enough to use in a game.

    As I understand the problem, identifying the melds can be difficult since a single card could be used in more than one meld. For example the seven cards {4H, 4D, 4S, 4C, 5C, 6C, 7C} could break into two different fully melded hands, first {{4H, 4D, 4S}, {4C, 5C, 6C, 7C}} and second {{4H, 4D, 4S, 4C}, {5C, 6C, 7C}}. There are also other melds in these seven cards that don't resolve fully melded hands, such as {4D, 4S, 4C}.

    The first brute force method (that I wouldn't use) would be to take all Permutations of 10 cards, check the first three cards for a valid meld, the next three for a valid meld and finally the last four for a valid meld. This loop would iterate 10! = 3,628,800 times each time the hand changed.

    The second, less forceful method (that I probably wouldn't use) would be to take the Combinations of 10 choose 3 cards and check for the first meld. This outer loop would only execute (10 choose 3) = 120 times. If and only if a meld is found, evaluate the remaining 7 cards with another Combination of 7 choose 3 cards. This inner loop would only iterate 35 times and would not be needed most of the time. Finally, check the last 4 cards for a meld to make the final determination. Worst case, the product of the two loops would be 4200 checks, but in practice would be much fewer.

    Finally, we can make some observations about the cards that would make our lives easier if we apply some sorting and scanning. If we sort by rank (and ignore suit) we can easily determine the melds that are sets of like ranks, call these m1. (Note that a set of 4 will produce 5 possible melds). If we re-sort by suit and then rank, we can easily determine the melds that are runs, call these m2. (Note that a run of 4 will produce 3 possible melds). Then, we can union these two sets of melds together to see all possible melds in the hand. Worst case, a hand will have 10 possible melds at once. If three or more melds are found, use a Combination across the melds choosing 3 melds. If the count of unique cards within the combination-of-3 meld-set is 10, then the hand is fully melded. This algorithm is likely the most complex, but would have the best average case performance. Note also that the hard work of finding the melds in the sorted sequence is not handled by the classes presented here.
    [/quote]

    Sunday, March 22, 2009 4:49 AM