1 module nxt.combinations;
2 
3 /** Given non-negative integers $(D m) and $(D n), generate all size $(D m)
4    combinations of the integers from 0 to $(D n)-1 in sorted order (each
5    combination is sorted and the entire table is sorted).
6 
7    For example, 3 comb 5 is
8    0 1 2
9    0 1 3
10    0 1 4
11    0 2 3
12    0 2 4
13    0 3 4
14    1 2 3
15    1 2 4
16    1 3 4
17    2 3 4
18 
19    See_Also: http://rosettacode.org/wiki/Combinations
20 */
21 struct Combinations(T, bool copy = true, bool useArray = true)
22 {
23     import std.container: Array;
24     import std.traits: Unqual;
25 
26     static if (useArray)
27         alias Indices = Array!size_t;
28     else
29         alias Indices = size_t[];
30 
31     Unqual!T[] pool, front;
32     size_t r, n;
33     bool empty = false;
34 
35     Indices indices;
36 
37     size_t len;
38     bool lenComputed = false;
39 
40     this(T[] pool_, in size_t r_) // pure nothrow @safe
41     {
42         this.pool = pool_.dup;
43         this.r = r_;
44         this.n = pool.length;
45         if (r > n)
46             empty = true;
47 
48         indices.length = r;
49 
50         size_t i;
51 
52         i = 0;
53         foreach (ref ini; indices[])
54             ini = i++;
55 
56         front.length = r;
57 
58         i = 0;
59         foreach (immutable idx; indices[])
60             front[i++] = pool[idx];
61     }
62 
63     @property size_t length() /*logic_const*/ // pure nothrow @nogc
64     {
65         static size_t binomial(size_t n, size_t k) // pure nothrow @safe @nogc
66         in
67         {
68             assert(n > 0, "binomial: n must be > 0.");
69         }
70         do
71         {
72             if (k < 0 || k > n)
73                 return 0;
74             if (k > (n / 2))
75                 k = n - k;
76             size_t result = 1;
77             foreach (size_t d; 1 .. k + 1) {
78                 result *= n;
79                 n--;
80                 result /= d;
81             }
82             return result;
83         }
84 
85         if (!lenComputed)
86         {
87             // Set cache.
88             len = binomial(n, r);
89             lenComputed = true;
90         }
91         return len;
92     }
93 
94     void popFront() // pure nothrow @safe
95     {
96         if (!empty)
97         {
98             bool broken = false;
99             size_t pos = 0;
100             foreach_reverse (immutable i; 0 .. r)
101             {
102                 pos = i;
103                 if (indices[i] != i + n - r)
104                 {
105                     broken = true;
106                     break;
107                 }
108             }
109             if (!broken)
110             {
111                 empty = true;
112                 return;
113             }
114             indices[pos]++;
115             foreach (immutable j; pos + 1 .. r)
116                 indices[j] = indices[j - 1] + 1;
117             static if (copy)
118                 front = new Unqual!T[front.length];
119 
120             size_t i = 0;
121             foreach (immutable idx; indices[])
122             {
123                 front[i] = pool[idx];
124                 i++;
125             }
126         }
127     }
128 }
129 
130 auto combinations(bool copy = true, T, bool useArray = false)(T[] items, in size_t k)
131 in
132 {
133     assert(items.length, "combinations: items can't be empty.");
134 }
135 do
136 {
137     return Combinations!(T, copy, useArray)(items, k);
138 }
139 
140 unittest
141 {
142     import std.algorithm: equal, map;
143     // assert(equal([1, 2, 3, 4].combinations!false(2), [[3, 4], [3, 4], [3, 4], [3, 4], [3, 4], [3, 4]]));
144     enum solution = [[1, 2],
145                      [1, 3],
146                      [1, 4],
147                      [2, 3],
148                      [2, 4],
149                      [3, 4]];
150     assert(equal([1, 2, 3, 4].combinations!true(2), solution));
151     assert(equal([1, 2, 3, 4].combinations(2).map!(x => x), solution));
152 }
153 
154 import std.range.primitives : isInputRange;
155 
156 /** All Unordered Element Pairs (2-Element Subsets) of a $(D Range).
157 
158     TODO Add template parameter to decide if .array should be used internally.
159 
160     See_Also: http://forum.dlang.org/thread/iqkybajwdzcvdytakgvw@forum.dlang.org#post-vhufbwsqbssyqwfxxbuu:40forum.dlang.org
161     See_Also: https://issues.dlang.org/show_bug.cgi?id=6788
162     See_Also: https://issues.dlang.org/show_bug.cgi?id=7128
163 */
164 auto pairwise(R)(R r)
165 if (isInputRange!R)
166 {
167     struct Pairwise(R)
168     {
169         import core.internal.traits : Unqual;
170         import std.traits : ForeachType;
171         import std.typecons: Tuple;
172 
173         alias UR = Unqual!R;
174         alias E = ForeachType!UR;
175         alias Pair = Tuple!(E, E);
176 
177         import std.range.primitives : isRandomAccessRange, hasLength;
178         import std.traits : isNarrowString;
179 
180         static if (isRandomAccessRange!R &&
181                    hasLength!R &&
182                    !isNarrowString!R)
183         {
184 
185             this(R r_)
186             {
187                 this._input = r_;
188                 j = 1;
189             }
190 
191             @property bool empty()
192             {
193                 return j >= _input.length;
194             }
195 
196             @property Pair front()
197             {
198                 return Pair(_input[i], _input[j]);
199             }
200 
201             void popFront()
202             {
203                 if (j >= _input.length - 1)
204                 {
205                     i++;
206                     j = i + 1;
207                 }
208                 else
209                 {
210                     j++;
211                 }
212             }
213             private size_t i, j;
214         }
215         else // isInputRange!UR
216         {
217             import std.range : dropOne;
218             this(R r_)
219             {
220                 this._input = r_;
221                 i = r_;
222                 if (!i.empty)
223                     j = i.dropOne;
224                 else
225                     j = UR.init;
226             }
227 
228             @property bool empty()
229             {
230                 return j.empty;
231             }
232 
233             @property Pair front()
234             {
235                 return Pair(i.front,
236                             j.front);
237             }
238 
239             void popFront()
240             {
241                 j.popFront();
242                 if (j.empty)
243                 {
244                     i.popFront();
245                     j = i.dropOne;
246                 }
247             }
248             private UR i, j; // temporary copies of $(D _input)
249         }
250 
251     private:
252         UR _input;
253     }
254 
255     return Pairwise!R(r);
256 }
257 
258 /// test RandomAccessRange input
259 unittest
260 {
261     import std.algorithm: equal, filter;
262     import std.typecons: Tuple;
263 
264     assert((new int[0]).pairwise.empty);
265     assert([1].pairwise.empty);
266 
267     alias T = Tuple!(int, int);
268     assert(equal([1, 2].pairwise,
269                  [T(1, 2)]));
270     assert(equal([1, 2, 3].pairwise,
271                  [T(1, 2), T(1, 3), T(2, 3)]));
272     assert(equal([1, 2, 3, 4].pairwise,
273                  [T(1, 2), T(1, 3), T(1, 4),
274                   T(2, 3), T(2, 4), T(3, 4)]));
275 }
276 
277 /// test ForwardRange input
278 unittest
279 {
280     import std.algorithm: equal, filter;
281     import std.array : array;
282 
283     auto p = [1].filter!"a < 4".pairwise;
284     assert(p.empty);
285 
286     assert(equal(p.array,
287                  [1].pairwise.array));
288 
289     assert(equal([1, 2, 3, 4].filter!"a < 4".pairwise,
290                  [1, 2, 3].pairwise));
291 }