C# Algorithm for Combinations/Permutations of a defined range of integers

Question

I am trying to generate a list of unique combinations/permutations of 3 allowable values for 20 different participants (each of the 20 participants can be assigned a value of either 1, 2, or 3).

An example of one combination would be an array on length 20 with all ones like such:

{ 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 }

...and everything possible all the way up to

{ 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3 }

where each value in the array can be 1, 2 or 3.

I am stuck on writing my GetAllCombinations() function and I looked at some articles on permutation, but everything I have found is just confusing me more. I am not even sure if permutation is what I need here

So far I have this:

public List<int[]> GetValidCombinations()
{
    const int positions = 20;
    int[] acceptableValues = new int[3] { 1, 2, 3 };

    //DO I USE PERMUTATION HERE TO BUILD MY ARRAY LIST OF ALL POSSIBLE COMBINATIONS?
    var allPossibleCombinations = GetAllCombinations(positions, acceptableValues);

    List<int[]> validList = new List<int[]>();
    foreach (var combination in allPossibleCombinations)
    {
        //omited for berevity but I would
        //do some other validations here...
        if (true)
        {
            validList.Add(combination);
        }
    }

    return validList;
}
public List<int[]> GetAllCombinations(int positions, int[] acceptableValues)
{
    //For now returning null because I 
    //don't know How the heck to do this...
    return null;
}

I have looked at some examples of permutation and I tried to use something like this below, but it did not produce what I was looking for:

static IEnumerable<IEnumerable<T>>
GetPermutations<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new T[] { t });
    return GetPermutations(list, length - 1)
        .SelectMany(t => list.Where(o => !t.Contains(o)),
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

public void Test()
{
    const int k = 20;
    var n = new[] { 1, 2, 3 };

    var combinations = GetPermutations(n, k);
    //DOES NOT WORK FOR WHAT I NEED
}

Running Test() worked with k was 3 or less but returned nothing if k was greater then 3.

Linh Nguyen · Accepted Answer · 2020-03-25 11:14:03Z

1

Try this:

    public static List<int[]> GetAllCombinations(int position, int[] acceptableVaues)
    {
        List<int[]> result = new List<int[]>();

        int[] parent = new int[] { };
        result = AddAPosition(parent, acceptableVaues);

        while(position > 1)
        {
            var tmpResult = new List<int[]>();
            foreach(var _parent in result)
            {
                tmpResult.AddRange(AddAPosition(_parent, acceptableVaues));
            }

            position--;
            result = tmpResult;
        }
        return result;
    }

    public static List<int[]> AddAPosition(int[] parent, int[] acceptableValues)
    {
        List<int[]> result = new List<int[]>();
        for (int i = 0; i< acceptableValues.Length; i++)
        {
            var anArray = new int[parent.Length + 1];
            for (int j = 0; j< parent.Length; j++)
            {
                anArray[j] = parent[j];
            }

            anArray[parent.Length] = acceptableValues[i];
            result.Add(anArray);
        }
        return result;
    }

answered Mar 25, 2020 at 11:14

Linh Nguyen

1,1388 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ben Over a year ago

This has been very helpful and guided me in learning a lot about this topic. This works great when my positions are 15 or less, but unfortunately because of the size I am running out of memory when it gets to generating the 15th round of possibilities. I may be running into a difficult situation that may not be easily solved just because of the sheer number of combinations. Any suggestions to do this with less memory would be appreciated although I realize it may just not be possible. Thanks again! - Ben

Ben Over a year ago

After looking at the debugger it looks like my output would theoretically result in 3 ^20 combinations - roughly 3.5 billion combinations. I am guessing I am up against a behemoth here.

Collectives™ on Stack Overflow

C# Algorithm for Combinations/Permutations of a defined range of integers

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related