SHOW:
|
|
- or go back to the newest paste.
| 1 | using System; | |
| 2 | using System.Collections.Generic; | |
| 3 | ||
| 4 | namespace _21.GenerateCombinations | |
| 5 | {
| |
| 6 | class Program | |
| 7 | {
| |
| 8 | static void Main(string[] args) | |
| 9 | - | {
|
| 9 | + | |
| 10 | //Same as commented input code below | |
| 11 | int n; | |
| 12 | int k; | |
| 13 | InputNAndK(out n, out k); | |
| 14 | ||
| 15 | //You can use "#region" to hide blocks of code or comments. | |
| 16 | #region | |
| 17 | /* | |
| 18 | Console.Write("Enter n: ");
| |
| 19 | int n = int.Parse(Console.ReadLine()); | |
| 20 | ||
| 21 | Console.Write("Enter k: ");
| |
| 22 | int k = int.Parse(Console.ReadLine()); | |
| 23 | */ | |
| 24 | #endregion | |
| 25 | - | if (n<0 || k< 0) |
| 25 | + | |
| 26 | if (n <= 0) | |
| 27 | {
| |
| 28 | - | return; |
| 28 | + | |
| 29 | return; | |
| 30 | } | |
| 31 | ||
| 32 | if (n < 0 || k < 0) | |
| 33 | {
| |
| 34 | Console.WriteLine("Both n and k must be greater than 0,");
| |
| 35 | return; | |
| 36 | } | |
| 37 | ||
| 38 | if (n < k) | |
| 39 | - | // method of the type "InitializeArray( combination);" |
| 39 | + | |
| 40 | - | List<int> list = new List<int>(n) ; |
| 40 | + | |
| 41 | return; | |
| 42 | - | |
| 42 | + | |
| 43 | ||
| 44 | - | |
| 44 | + | |
| 45 | - | InitializeArray( combination); |
| 45 | + | |
| 46 | //method of the type "InitializeArray( combination);", | |
| 47 | //where combination is array of some size. | |
| 48 | List<int> list = new List<int>(n); | |
| 49 | InitializeList(list, n); | |
| 50 | ||
| 51 | int[] combination = new int[k]; | |
| 52 | InitializeArray(combination); | |
| 53 | ||
| 54 | bool nextCombinationExists = true; | |
| 55 | //Returns all combinations without repetitions | |
| 56 | do | |
| 57 | {
| |
| 58 | PrintCombination(combination); | |
| 59 | nextCombinationExists = NextIndexCombination(list.Count, k, combination); | |
| 60 | ||
| 61 | - | for (int i = 1; i <=count ; i++) |
| 61 | + | |
| 62 | } | |
| 63 | - | list.Add(i); |
| 63 | + | |
| 64 | private static void InputNAndK(out int n, out int k) | |
| 65 | {
| |
| 66 | Console.Write("Enter n: ");
| |
| 67 | n = int.Parse(Console.ReadLine()); | |
| 68 | ||
| 69 | Console.Write("Enter k: ");
| |
| 70 | k = int.Parse(Console.ReadLine()); | |
| 71 | - | Console.Write((comb[i] + 1) +" "); |
| 71 | + | |
| 72 | - | |
| 72 | + | |
| 73 | private static void InitializeList(List<int> list, int count) | |
| 74 | {
| |
| 75 | for (int i = 1; i <= count; i++) | |
| 76 | - | |
| 76 | + | |
| 77 | list.Add(i); | |
| 78 | } | |
| 79 | } | |
| 80 | ||
| 81 | private static void PrintCombination(int[] comb) | |
| 82 | {
| |
| 83 | for (int i = 0; i < comb.Length; i++) | |
| 84 | {
| |
| 85 | Console.Write((comb[i] + 1) + " "); | |
| 86 | } | |
| 87 | Console.WriteLine(); | |
| 88 | } | |
| 89 | ||
| 90 | //Explanation of the method. | |
| 91 | #region | |
| 92 | /*The method generates next k-combination of indexes without repetition, | |
| 93 | for given n, k and current combination of indexes. | |
| 94 | ||
| 95 | *The logic behind the method: | |
| 96 | 1. The idea of int[] arrayOfIndexes is to represent indexes in another array. After changing | |
| 97 | values in arrayOfIndexes, we can access the values in the other array: | |
| 98 | ||
| 99 | arrayOfIndexes = {0, 1, 2} ; otherArray = {'a', 'b', 'c', 'd', 'e'} result: a, b, c
| |
| 100 | arrayOfIndexes = {0, 1, 3} ; otherArray = {'a', 'b', 'c', 'd', 'e'} result: a, b, d
| |
| 101 | arrayOfIndexes = {0, 1, 4} ; otherArray = {'a', 'b', 'c', 'd', 'e'} result: a, b, e
| |
| 102 | arrayOfIndexes = {0, 2, 3} ; otherArray = {'a', 'b', 'c', 'd', 'e'} result: a, c, d
| |
| 103 | .................................................................................. | |
| 104 | ||
| 105 | NOTE: in case of otherArray of type {1, 2, 3, .... n} arrayOfIndexes[i] + 1 == otherArray[i]
| |
| 106 | ||
| 107 | 2. int[] arrayOfIndexes is a reference type - that means that the method modifies it. | |
| 108 | See: http://pastebin.com/R6kbsqJw | |
| 109 | ||
| 110 | 3. See http://en.wikipedia.org/wiki/File:Combinations_without_repetition;_5_choose_3.svg | |
| 111 | We have combinations of 5 items taken 3 at a time, without repetition | |
| 112 | ||
| 113 | What happens in the picture: | |
| 114 | 1. The last item increases by one until it reaches its max value - the max | |
| 115 | value of the last item is 5. | |
| 116 | 2. Then, the next item makes the same thing, only its max value is 5 - 1. | |
| 117 | 3. The the next - with max value 5 - 2. And so on... | |
| 118 | .................... | |
| 119 | .................... | |
| 120 | So, there is a max value that each item has to reach before the next item is changed. | |
| 121 | Max value formula: maxIndex - (kClass - 1 - currentIndex), where | |
| 122 | - maxIndex = n - 1, where n - the count of all items | |
| 123 | - kClass = k, the class of the combination | |
| 124 | - currentIndex - the index of the current item in arrayOfIndexes. | |
| 125 | ||
| 126 | How the algoritm works: | |
| 127 | ||
| 128 | foreach item in arrayOfIndexes(but starting from the last and going to the first) we check | |
| 129 | if this item has not reached its max value | |
| 130 | - if it hasn`t: | |
| 131 | 1. get index of that item (itemIndex = currentIndex;) | |
| 132 | 2. arrayOfIndexes[itemIndex]++; | |
| 133 | 3. every nextItem = previous item + 1 | |
| 134 | 4. return true (combinationExists) | |
| 135 | - if it has: | |
| 136 | 1. check next item while find such that hasn`t or iterate through all items. | |
| 137 | ||
| 138 | If all items have reached its max value. "itemIndex" remains equal to "kClass". | |
| 139 | In that case no more combinations exist. | |
| 140 | */ | |
| 141 | #endregion | |
| 142 | static bool NextIndexCombination(int elementsCount, int kClass, int[] arrayOfIndexes) | |
| 143 | {
| |
| 144 | int maxIndex = elementsCount - 1; | |
| 145 | // Find the first item that has not reached its maximum value. | |
| 146 | int itemIndex = kClass; | |
| 147 | for (int currentIndex = arrayOfIndexes.Length - 1; currentIndex >= 0; currentIndex--) | |
| 148 | {
| |
| 149 | if (arrayOfIndexes[currentIndex] < maxIndex - (kClass - 1 - currentIndex)) | |
| 150 | {
| |
| 151 | itemIndex = currentIndex; | |
| 152 | break; | |
| 153 | } | |
| 154 | } | |
| 155 | ||
| 156 | // No more combinations to be generated. Every index has reached its | |
| 157 | // maximum value. | |
| 158 | if (itemIndex == kClass) | |
| 159 | - | static void InitializeArray(int[] combination) |
| 159 | + | |
| 160 | return false; | |
| 161 | } | |
| 162 | // Genereate the next combination in lexographical order. | |
| 163 | - | combination[i] = i; |
| 163 | + | |
| 164 | - | } |
| 164 | + | |
| 165 | {
| |
| 166 | arrayOfIndexes[i] = arrayOfIndexes[i - 1] + 1; | |
| 167 | } | |
| 168 | ||
| 169 | return true; | |
| 170 | } | |
| 171 | ||
| 172 | static void InitializeArray(int[] combination) | |
| 173 | {
| |
| 174 | for (int i = 0; i < combination.Length; i++) | |
| 175 | {
| |
| 176 | combination[i] = i; | |
| 177 | } | |
| 178 | } | |
| 179 | } | |
| 180 | } |