View difference between Paste ID: Qba9fnPe and 9NCWGNdF
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
}