0

Using C#, I need to find out all the combinations of the possible outcomes of UK National Lottery (excluding Bonus Number). So I am trying to get all the combination of six numbers from the unique combinations of Numbers 1 to 59. Each combination consists of non-repetitive numbers and order is irrelevant.

The output of all the valid combinations are:
1 2 3 4 5 6
1 2 3 4 5 7
... so on
1 2 3 4 5 59
1 2 3 4 6 7
... so on
53 54 55 56 57 58
53 54 55 56 57 59
54 55 56 57 58 59

As there are more than 45 million combinations, I have tried to implement it with one jagged array as result set but it is throwing out of memory exception.
So I have split it in two Result sets as in the below code but it is still throwing the same exception.

How can I get all the combinations in either two result sets or one single result set?
In the below code, I have used Jagged Arrays but the result set can be of any object type.
I obviously need the algorithm with the best performance with regard to both Time and Space complexity.
Thanks for your help in advance.

 private void GetAllCombinationsForSixNumbers(out int[][] arrayOfAllCombinationsFirstSet, out int[][] arrayOfAllCombinationsSecondSet)
    {
        arrayOfAllCombinationsFirstSet = new int[25000000][];
        arrayOfAllCombinationsSecondSet = new int[25000000][];

        for (int eachArray = 0; eachArray < arrayOfAllCombinationsFirstSet.Length; eachArray++)
        {
            arrayOfAllCombinationsFirstSet[eachArray] = new int[6];
            arrayOfAllCombinationsSecondSet[eachArray] = new int[6];
        }
        int arrayCurrentRowIndex = 0, arrayCurrentRowIndexForSecondArray = 0;

        for (int firstNumber = 1; firstNumber < 59; firstNumber++)
        {
            for (int secondNumber = firstNumber + 1; secondNumber <= 59; secondNumber++)
            {
                for (int thirdNumber = secondNumber + 1; thirdNumber <= 59; thirdNumber++)
                {
                    for (int fourthNumber = thirdNumber + 1; fourthNumber <= 59; fourthNumber++)
                    {
                        for (int fifthNumber = fourthNumber + 1; fifthNumber <= 59; fifthNumber++)
                        {
                            for (int sixthNumber = fifthNumber + 1; sixthNumber <= 59; sixthNumber++)
                            {
                                if (arrayCurrentRowIndex < arrayOfAllCombinationsFirstSet.Length)
                                {
                                    arrayOfAllCombinationsFirstSet[arrayCurrentRowIndex][0] = firstNumber;
                                    arrayOfAllCombinationsFirstSet[arrayCurrentRowIndex][1] = secondNumber;
                                    arrayOfAllCombinationsFirstSet[arrayCurrentRowIndex][2] = thirdNumber;
                                    arrayOfAllCombinationsFirstSet[arrayCurrentRowIndex][3] = fourthNumber;
                                    arrayOfAllCombinationsFirstSet[arrayCurrentRowIndex][4] = fifthNumber;
                                    arrayOfAllCombinationsFirstSet[arrayCurrentRowIndex][5] = sixthNumber;
                                    arrayCurrentRowIndex++;
                                }
                                else
                                {
                                    arrayOfAllCombinationsSecondSet[arrayCurrentRowIndexForSecondArray][0] = firstNumber;
                                    arrayOfAllCombinationsSecondSet[arrayCurrentRowIndexForSecondArray][1] = secondNumber;
                                    arrayOfAllCombinationsSecondSet[arrayCurrentRowIndexForSecondArray][2] = thirdNumber;
                                    arrayOfAllCombinationsSecondSet[arrayCurrentRowIndexForSecondArray][3] = fourthNumber;
                                    arrayOfAllCombinationsSecondSet[arrayCurrentRowIndexForSecondArray][4] = fifthNumber;
                                    arrayOfAllCombinationsSecondSet[arrayCurrentRowIndexForSecondArray][5] = sixthNumber;
                                    arrayCurrentRowIndexForSecondArray++;
                                }
                            }
                        }
                    }
                }
            }
        }         

    }
Sanjay M
  • 21
  • 5
  • Why are you using arrays instead of better/easier-to-work-with collections, like List? – rory.ap Oct 06 '16 at 11:34
  • Also, glancing briefly at your code...it seems like a recursive function would be cleaner than all those nested loops. – rory.ap Oct 06 '16 at 11:35
  • 1
    Why do you need 45,057,474 arrays in your program? What do you want to do with all of them? – Dialecticus Oct 06 '16 at 11:39
  • See this for a Linq solution : http://stackoverflow.com/questions/33336540/how-to-use-linq-to-find-all-combinations-of-n-items-from-a-set-of-numbers - though expanding the result set of Enumerable.Range(1, 59).DifferentCombinations(6) does cause an out of memory exception. – PaulF Oct 06 '16 at 11:48
  • Not that I dont like Linq solution , but I don't think this recursion will be best solution in so many options. – kuskmen Oct 06 '16 at 11:50
  • @rory.ap - Do you suggest to use List of arrays or List of custom objects? – Sanjay M Oct 06 '16 at 12:59
  • @Dialecticus - I need it as I am going to do shuffling operation later and then retreive x number of random combinations. x could be in thousands or millions. – Sanjay M Oct 06 '16 at 13:02
  • If your goal is to generate `x` random combinations then you can do it without having so many objects in memory. [There is a way](https://msdn.microsoft.com/en-us/library/aa289166(v=vs.71).aspx) do convert a single number in range [1-45,057,474] (lexicographical index) to one exact combination. Then you just have to generate `x` unique random numbers, and even for this you don't need a giant array of 45 million numbers. – Dialecticus Oct 06 '16 at 13:10
  • The Linq solution results in lazy (deferred) execution & you could evaluate x values without all 45million combinations being evaluated. – PaulF Oct 06 '16 at 13:52
  • @PaulF yes if you want first x values, but what happens if you want random x values, one of which may be close to 45 million? – Dialecticus Oct 06 '16 at 15:19
  • @Dialecticus: Thanks for your suggestion. As generating the 'x' random numbers is required to be done many times and the 45 million combinations are constant, I am planning to store these 45 million numbers in sql database table, index the data for better performance. I can select the x random unique indexes of the table every time. I am using sql as implementing it in c# is very costly with regard to memory. – Sanjay M Oct 06 '16 at 15:39
  • @Dialecticus: it takes some time - but as it is not "evaluating" the values in between - in the sense of allocating memory - then the out of memory exception will be avoided. – PaulF Oct 06 '16 at 16:10
  • @SanjayM please do not use database for something that can be done without database, and also faster, and using less memory. To generate a random number in range 0-45,057,474 you can use [this answer](http://stackoverflow.com/a/13095144). To generate `x` unique such numbers just add them to `HashSet` until its `Count` property reaches `x`. To convert one such number to appropriate combination use the code from the link I posted in a previous comment. It will be faster than a database. – Dialecticus Oct 06 '16 at 19:05

2 Answers2

2

So, you generating values from [1 2 3 4 5 6] to [54 55 56 57 58 59] in numeral system with base 59, excluding zero. Excluded zero is not a problem at all, you just need to make shift to left, so 1 becomes 0, 2 becomes 1 and so on. So your borders become like this:

[0 1 2 3 4 5]
....
[53 54 55 56 57 58]

After that, you can create function that will map index with base 10 (decimal) to exact value in your array.

For this you need to convert your index with base 10 to index in numeral system with base 59. For example, I want to take value from your array by index 123:

123 => [2 5]

Make addition in this numeral system with start index:

[0 1 2 3 4 5] + [2 5] = [0 1 2 3 6 10]

Then you just shift it backward: 

[1 2 3 4 7 11]

As for repetition - just filter it. It's gross but performace impact would be small.

eocron
  • 6,885
  • 1
  • 21
  • 50
  • `base 60` only if `0` is allowed. – Jeroen van Langen Oct 06 '16 at 11:43
  • Not too sure I understand this - what if I want element at index 119 - wouldn't that give 119 => [2 1] so addition would be [0 1 2 3 4 5] + [2 1] = [0 1 2 3 6 6] & shifting [1 2 3 4 7 7] - resulting in a duplicated number. – PaulF Oct 06 '16 at 12:02
  • Hmm, I need to think about it some more. As solution in mean time, you can just filter it =) Persentage of repetition is not so big, so it won't be considerable impact. – eocron Oct 06 '16 at 12:06
  • I think you may spend more time filtering out the unrequired results - there are 59! possible results in your solution = approx 1.4e80 of which only 45 million are valid. – PaulF Oct 06 '16 at 12:15
  • Firstly, you convert [53 54 55 56 57 58] to 10-base index and border it out. Secondly you filter out repetitions. Repetition occurs much lesser than valid numbers. – eocron Oct 06 '16 at 12:41
  • To go from [0 1 2 3 4 5] to [53 54 55 56 57 58] you would need to add [53 53 53 53 53] which in base 10 is 22,164,361,129. Out of that sequence of numbers only 45,057,474 - which leaves 22,119,303,655 repetitions (i.e. approx. 0.2% unique, 99.8% repetitions). – PaulF Oct 06 '16 at 13:04
0

If you absolutely need so many arrays (I really don't know why you would) then you can change all int to byte except int eachArray because byte needs the least amount of memory in the CLR. Additionally you can reduce your array sizes from 25000000 to 22600000.

In my tests the byte arrays (of your otherwise unchanged code) barely fit into the available memory of a 32-bit process if you create them in an otherwise empty console application.

If they still don't fit into memory in your specific application then you have to change your process to 64-bit (with enough free RAM in the system).

However, it's much better to just generate the combinations lazily and on the fly - only as much as you need in the current situation.

haindl
  • 3,111
  • 2
  • 25
  • 31
  • I have tried using byte but still the same issue. I am using 64-bit machine and reduced the array size. I need to store the data in sql as in c# it is taking lot of memory. – Sanjay M Oct 06 '16 at 15:29
  • @SanjayM You need to change your .net process to 64-bit. A 64-bit machine alone is not enough. You can change this in the project properties --> Build --> Platform target --> "x64". – haindl Oct 06 '16 at 15:37