Generating ordered lists of lists of integers
Generating an ordered list of all pairs of integers
foreach (var i in ListOfAllListsOfIntegersOfLengthNUpToHeight(
7, 2,
NegativePolicy.PositiveOnly, ZeroPolicy.NoZeroes))
Console.WriteLine(String.Join("/", i));
Output
1/1
1/2
2/1
1/3
2/2
3/1
1/4
2/3
3/2
4/1
1/5
2/4
3/3
4/2
5/1
1/6
2/5
3/4
4/3
5/2
6/1
Generating an ordered list of all lists of integers
foreach (var i in ListOfAllListsOfIntegers(4))
Console.WriteLine(String.Join(", ", i));
Output
1
-1
2
-2
1, 0
-1, 0
3
-3
1, 1
1, -1
-1, 1
-1, -1
2, 0
-2, 0
1, 0, 0
-1, 0, 0
Code
public enum ZeroPolicy
{
AllowZeroes,
NoLeadingZeroes,
NoZeroes
}
public enum NegativePolicy
{
AllIntegers,
PositiveOnly
}
/// <summary>
/// Returns a list of all list of integers up to a height
/// <see cref="upToHeight"/> where the height of a list of integers is defined
/// as the length of the list plus the sum of the absolute values of all the
/// integers in the list.
/// </summary>
public static IEnumerable<IEnumerable<int>> ListOfAllListsOfIntegers(
int upToHeight)
{
for (int height1 = 2; height1 <= upToHeight; height1++)
{
foreach (var l in ListOfAllListsOfIntegersOfLengthN(height1,
2, NegativePolicy.PositiveOnly, ZeroPolicy.NoZeroes))
{
var ll = l.ToList();
var length = ll[0];
var height2 = ll[1];
foreach (var x in ListOfAllListsOfIntegersOfLengthN(height2,
length, NegativePolicy.AllIntegers, ZeroPolicy.NoLeadingZeroes))
yield return x;
}
}
}
/// <summary>
/// Returns a list of all lists of integers of length <see cref="length"/> up to
/// a height <see cref="upToHeight"/> where the height of a list of integers is
/// define as the sum of the absolute values of all the integers in the list.
/// </summary>
public static IEnumerable<IEnumerable<int>> ListOfAllListsOfIntegersOfLengthNUpToHeight(
int upToHeight, int length, NegativePolicy allowNegative,
ZeroPolicy zeroPolicy = ZeroPolicy.AllowZeroes)
{
var startHeight = 1;
if (zeroPolicy == ZeroPolicy.AllowZeroes) startHeight = 0;
for (int h = startHeight; h <= upToHeight; h++)
{
foreach (var x in ListOfAllListsOfIntegersOfLengthN(h, length,
allowNegative, zeroPolicy))
{
yield return x;
}
}
}
/// <summary>
/// Returns a list of all lists of integers of length <see cref="length"/> and of
/// height <see cref="height"/> where the height of a list of integers is defined
/// as the sum of the absolute values of all the integers in the list.
/// </summary>
public static IEnumerable<IEnumerable<int>> ListOfAllListsOfIntegersOfLengthN(
int height, int length, NegativePolicy allowNegative,
ZeroPolicy zeroPolicy = ZeroPolicy.AllowZeroes)
{
if (height == 0)
{
yield return Enumerable.Repeat(0, length);
}
else if (length == 1)
{
yield return new List<int> {height};
if (allowNegative == NegativePolicy.AllIntegers)
yield return new List<int> {-height};
}
else
{
int startVal;
int endVal;
var subsequentZeroPolicy = zeroPolicy;
switch (zeroPolicy)
{
case ZeroPolicy.NoLeadingZeroes:
startVal = 1;
endVal = height;
subsequentZeroPolicy = ZeroPolicy.AllowZeroes;
break;
case ZeroPolicy.AllowZeroes:
startVal = 0;
endVal = height;
break;
case ZeroPolicy.NoZeroes:
startVal = 1;
endVal = height - length + 1;
break;
default:
throw new Exception();
}
for (int firstElement = startVal; firstElement <= endVal; firstElement++)
{
// Take first element in the list to be +i and use recursion to generate
// all possible lists of the remaining elements.
var allPossibleRestOfLists = ListOfAllListsOfIntegersOfLengthN(
height - firstElement, length - 1,
allowNegative, subsequentZeroPolicy).ToList();
var firstElementPositive = firstElement;
foreach (var y in allPossibleRestOfLists.Select(restOfList => new[]
// Add first element to beginning
{new[] {firstElementPositive}, restOfList}.SelectMany(y => y)))
// and yield
yield return y;
// Take first element in the list to be -i and attach to all possible
// lists of remaining elements
if (allowNegative == NegativePolicy.AllIntegers && firstElement != 0)
{
var firstElementNegative = -firstElement;
foreach (var y in allPossibleRestOfLists.Select(x => new[]
// Add first element to beginning
{ new[] {firstElementNegative}, x }.SelectMany(y => y)))
// and yield
yield return y;
}
}
}
}