Ordered partitions: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|C++}}: Remove vanity tags) |
(Added C#) |
||
Line 559: | Line 559: | ||
({ 2 4 },{ },{ 1 3 },), |
({ 2 4 },{ },{ 1 3 },), |
||
({ 3 4 },{ },{ 1 2 },),</pre> |
({ 3 4 },{ },{ 1 2 },),</pre> |
||
=={{header|C sharp}}== |
|||
<lang csharp>using System; |
|||
using System.Linq; |
|||
using System.Collections.Generic; |
|||
public static class OrderedPartitions |
|||
{ |
|||
public static void Main() { |
|||
var input = new [] { new[] { 0, 0, 0, 0, 0 }, new[] { 2, 0, 2 }, new[] { 1, 1, 1 } }; |
|||
foreach (int[] sizes in input) { |
|||
foreach (var partition in Partitions(sizes)) { |
|||
Console.WriteLine(partition.Select(set => set.Delimit(", ").Encase('{','}')).Delimit(", ").Encase('(', ')')); |
|||
} |
|||
Console.WriteLine(); |
|||
} |
|||
} |
|||
static IEnumerable<IEnumerable<int[]>> Partitions(params int[] sizes) { |
|||
var enumerators = new IEnumerator<int[]>[sizes.Length]; |
|||
var unused = Enumerable.Range(1, sizes.Sum()).ToSortedSet(); |
|||
var arrays = sizes.Select(size => new int[size]).ToArray(); |
|||
for (int s = 0; s >= 0; ) { |
|||
if (s == sizes.Length) { |
|||
yield return arrays; |
|||
s--; |
|||
} |
|||
if (enumerators[s] == null) { |
|||
enumerators[s] = Combinations(sizes[s], unused.ToArray()).GetEnumerator(); |
|||
} else { |
|||
unused.UnionWith(arrays[s]); |
|||
} |
|||
if (enumerators[s].MoveNext()) { |
|||
enumerators[s].Current.CopyTo(arrays[s], 0); |
|||
unused.ExceptWith(arrays[s]); |
|||
s++; |
|||
} else { |
|||
enumerators[s] = null; |
|||
s--; |
|||
} |
|||
} |
|||
} |
|||
static IEnumerable<T[]> Combinations<T>(int count, params T[] array) { |
|||
T[] result = new T[count]; |
|||
foreach (int pattern in BitPatterns(array.Length - count, array.Length)) { |
|||
for (int b = 1 << (array.Length - 1), i = 0, r = 0; b > 0; b >>= 1, i++) { |
|||
if ((pattern & b) == 0) result[r++] = array[i]; |
|||
} |
|||
yield return result; |
|||
} |
|||
} |
|||
static IEnumerable<int> BitPatterns(int ones, int length) { |
|||
int initial = (1 << ones) - 1; |
|||
int blockMask = (1 << length) - 1; |
|||
for (int v = initial; v >= initial; ) { |
|||
yield return v; |
|||
if (v == 0) break; |
|||
int w = (v | (v - 1)) + 1; |
|||
w |= (((w & -w) / (v & -v)) >> 1) - 1; |
|||
v = w & blockMask; |
|||
} |
|||
} |
|||
static string Delimit<T>(this IEnumerable<T> source, string separator) => string.Join(separator, source); |
|||
static string Encase(this string s, char start, char end) => start + s + end; |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
({}, {}, {}, {}, {}) |
|||
({1, 2}, {}, {3, 4}) |
|||
({1, 3}, {}, {2, 4}) |
|||
({1, 4}, {}, {2, 3}) |
|||
({2, 3}, {}, {1, 4}) |
|||
({2, 4}, {}, {1, 3}) |
|||
({3, 4}, {}, {1, 2}) |
|||
({1}, {2}, {3}) |
|||
({1}, {3}, {2}) |
|||
({2}, {1}, {3}) |
|||
({2}, {3}, {1}) |
|||
({3}, {1}, {2}) |
|||
({3}, {2}, {1})</pre> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |