CODEWITHSUNDEEP
c#permutation
Ben
Ben

Reputation: 1023

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

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.

Upvotes: 0

Views: 93

Answers (1)

Linh Nguyen
Linh Nguyen

Reputation: 1138

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

Upvotes: 1

Related Questions