# Generating ordered lists of lists of integers

Tags: set-theory

## Generating an ordered list of all pairs of integers

### Input

``````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

### Input

``````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,
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;
var height2 = ll;
foreach (var x in ListOfAllListsOfIntegersOfLengthN(height2,
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)
{
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;
}

}

}
}``````