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 | } |