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,
    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;
            }


        }

    }
}