Databases
StackOverflow2013
Postsdbo
PO
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    text
    copied!<p>The following code is written in C#.</p> <pre><code>class LineList&lt;T&gt; : List&lt;T[][]&gt; { public override string ToString() { var sb = new StringBuilder(); sb.Append(Count).AppendLine(" lines:"); foreach (var line in this) { if (line.Length &gt; 0) { foreach (var bucket in line) { sb.Append('{'); foreach (var item in bucket) { sb.Append(item).Append(','); } if (bucket.Length &gt; 0) { sb.Length -= 1; } sb.Append("}, "); } sb.Length -= 2; } sb.AppendLine(); } return sb.ToString(); } } class Permutor&lt;T&gt; { public T[] Items { get; private set; } public bool ReuseBuckets { get; set; } private T[] emptyBucket_; private Dictionary&lt;int, Dictionary&lt;int, T[]&gt;&gt; buckets_; // for memoization when ReuseBuckets=true public Permutor(T[] items) { ReuseBuckets = true; // faster and uses less memory Items = items; emptyBucket_ = new T[0]; buckets_ = new Dictionary&lt;int, Dictionary&lt;int, T[]&gt;&gt;(); } private T[] GetBucket(int index, int size) { if (size == 0) { return emptyBucket_; } Dictionary&lt;int, T[]&gt; forIndex; if (!buckets_.TryGetValue(index, out forIndex)) { forIndex = new Dictionary&lt;int, T[]&gt;(); buckets_[index] = forIndex; } T[] bucket; if (!forIndex.TryGetValue(size, out bucket)) { bucket = new T[size]; Array.Copy(Items, index, bucket, 0, size); forIndex[size] = bucket; } return bucket; } public LineList&lt;T&gt; GetLines(int bucketsPerLine) { var lines = new LineList&lt;T&gt;(); if (bucketsPerLine &gt; 0) { AddLines(lines, bucketsPerLine, 0); } return lines; } private void AddLines(LineList&lt;T&gt; lines, int bucketAllotment, int taken) { var start = bucketAllotment == 1 ? Items.Length - taken : 0; var stop = Items.Length - taken; for (int nItemsInNextBucket = start; nItemsInNextBucket &lt;= stop; nItemsInNextBucket++) { T[] nextBucket; if (ReuseBuckets) { nextBucket = GetBucket(taken, nItemsInNextBucket); } else { nextBucket = new T[nItemsInNextBucket]; Array.Copy(Items, taken, nextBucket, 0, nItemsInNextBucket); } if (bucketAllotment &gt; 1) { var subLines = new LineList&lt;T&gt;(); AddLines(subLines, bucketAllotment - 1, taken + nItemsInNextBucket); foreach (var subLine in subLines) { var line = new T[bucketAllotment][]; line[0] = nextBucket; subLine.CopyTo(line, 1); lines.Add(line); } } else { var line = new T[1][]; line[0] = nextBucket; lines.Add(line); } } } } </code></pre> <p>These calls...</p> <pre><code>var permutor = new Permutor&lt;int&gt;(new[] { 1, 2, 3 }); for (int bucketsPerLine = 0; bucketsPerLine &lt;= 4; bucketsPerLine++) { Console.WriteLine(permutor.GetLines(bucketsPerLine)); } </code></pre> <p>generate this output...</p> <pre><code>0 lines: 1 lines: {1,2,3} 4 lines: {}, {1,2,3} {1}, {2,3} {1,2}, {3} {1,2,3}, {} 10 lines: {}, {}, {1,2,3} {}, {1}, {2,3} {}, {1,2}, {3} {}, {1,2,3}, {} {1}, {}, {2,3} {1}, {2}, {3} {1}, {2,3}, {} {1,2}, {}, {3} {1,2}, {3}, {} {1,2,3}, {}, {} 20 lines: {}, {}, {}, {1,2,3} {}, {}, {1}, {2,3} {}, {}, {1,2}, {3} {}, {}, {1,2,3}, {} {}, {1}, {}, {2,3} {}, {1}, {2}, {3} {}, {1}, {2,3}, {} {}, {1,2}, {}, {3} {}, {1,2}, {3}, {} {}, {1,2,3}, {}, {} {1}, {}, {}, {2,3} {1}, {}, {2}, {3} {1}, {}, {2,3}, {} {1}, {2}, {}, {3} {1}, {2}, {3}, {} {1}, {2,3}, {}, {} {1,2}, {}, {}, {3} {1,2}, {}, {3}, {} {1,2}, {3}, {}, {} {1,2,3}, {}, {}, {} </code></pre> <p>The approximate size of the solution (bucketsPerLine * NumberOfLines) dominates the execution time. For these tests, N is the length of the input array and the bucketsPerLine is set to N as well.</p> <pre><code>N=10, solutionSize=923780, elapsedSec=0.4, solutionSize/elapsedMS=2286 N=11, solutionSize=3879876, elapsedSec=2.1, solutionSize/elapsedMS=1835 N=12, solutionSize=16224936, elapsedSec=10.0, solutionSize/elapsedMS=1627 N=13, solutionSize=67603900, elapsedSec=47.9, solutionSize/elapsedMS=1411 </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload