C# Алгоритм для комбинаций / перестановок определенного диапазона целых чисел

Question

Я пытаюсь создать список уникальных комбинаций / перестановок из 3 допустимых значений для 20 различных участников (каждому из 20 участников может быть присвоено значение 1, 2 или 3).

Примером одной комбинации может быть массив длиной 20 со всеми подобными:

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

... и все возможное вплоть до

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

, где каждое значение в массиве может быть 1, 2 или 3.

Я застрял при написании своей функции GetAllCombinations(), и я просмотрел несколько статей о перестановке, но все, что я нашел, просто сбивает меня с толку. Я даже не уверен, нужна ли мне здесь перестановка

Пока у меня есть это:

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

Я посмотрел несколько примеров перестановки и попытался использовать что-то подобное ниже , но он не выдал то, что я искал:

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
}

Запуск Test() работал с k было 3 или меньше, но ничего не возвращал, если k больше 3.

Answer 1

Попробуйте это:

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