C # Перестановка набора строк с учетом n и максимальной длины массива

Question

Как вы можете переставлять набор строк на основе заданной длины, я скажу, что 50 значений в массиве и хочу объединить только 24 значения, разделенные запятыми. Примеры: (строка1, строка2, строка3), но без повторения комбинации и порядок. У меня есть этот код ниже.

class Program
{
    static void Main(string[] args)
    {
        //var values1 = new[] { 1, 2, 3, 4, 5 };

        //foreach (var permutation in values1.GetPermutations())
        //{
        //    Console.WriteLine(string.Join(", ", permutation));
        //}

        var values2 = new[] { "asd", "das", "sad", "q1we", "asd" };

        foreach (var permutation in values2.GetPermutations())
        {
            Console.WriteLine(string.Join(",", permutation));
        }

        Console.ReadLine();
    }
}

public static class SomeExtensions
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> enumerable)
    {
        var array = enumerable as T[] ?? enumerable.ToArray();

        var factorials = Enumerable.Range(0, array.Length + 1)
            .Select(Factorial)
            .ToArray();

        for (var i = 0L; i < factorials[array.Length]; i++)
        {
            var sequence = GenerateSequence(i, array.Length - 1, factorials);

            yield return GeneratePermutation(array, sequence);
        }
    }

    private static IEnumerable<T> GeneratePermutation<T>(T[] array, IReadOnlyList<int> sequence)
    {
        var clone = (T[])array.Clone();

        for (int i = 0; i < clone.Length - 1; i++)
        {
            Swap(ref clone[i], ref clone[i + sequence[i]]);
        }

        return clone;
    }

    private static int[] GenerateSequence(long number, int size, IReadOnlyList<long> factorials)
    {
        var sequence = new int[size];

        for (var j = 0; j < sequence.Length; j++)
        {
            var facto = factorials[sequence.Length - j];

            sequence[j] = (int)(number / facto);
            number = (int)(number % facto);
        }

        return sequence;
    }

    static void Swap<T>(ref T a, ref T b)
    {
        T temp = a;
        a = b;
        b = temp;
    }

    private static long Factorial(int n)
    {
        long result = n;

        for (int i = 1; i < n; i++)
        {
            result = result * i;
        }

        return result;
    }
}

Как я могу объединить массив строк (24 значения) в 100 строк уникальной комбинации? Не могли бы вы объяснить, как и как лучше всего это сделать?

Answer 1

Я предлагаю использовать более детерминированный генератор перестановок. Соедините это с существующими методами расширения LINQ, такими как Select(), Distinct() и Take(), и вы получите то, что вам нужно:

var results = values2.Permutations(24)
                     .Select(p => String.Join(",", p))
                     .Distinct()
                     .Take(100);
foreach (var permutation in results)
    Console.WriteLine(permutation);

, где Permutations() реализован как метод расширения. Число 24 здесь указывает, сколько предметов должно быть в каждой перестановке. Это k в _n P _k .

Вызов Select() создает строковую строку со всеми элементами для конкретной перестановки.

Вызов Distinct() гарантирует, что мы получим только уникальные строки.

Вызов Take() ограничивает количество строк, которые мы собираем.

Вот наивная реализация, использующая рекурсию для генерации перестановок:

public static IEnumerable<T[]> Permutations<T>(this IEnumerable<T> source, int k)
{
    if (k < 0)
        throw new ArgumentOutOfRangeException(nameof(k), "May not be negative");

    var items = source.ToArray();
    if (k > items.Length)
        throw new ArgumentOutOfRangeException(nameof(k), "May not be bigger than the number of items in source");

    var buffer = new ArraySegment<T>(items, 0, k);
    return Permute(0);

    IEnumerable<T[]> Permute(int depth)
    {
        if (depth == k)
        {
            yield return buffer.ToArray();
            yield break;
        }

        for (int i = depth; i < items.Length; i++)
        {
            Swap(depth, i);
            foreach (var permutation in Permute(depth + 1))
                yield return permutation;
            Swap(depth, i);
        }
    }

    void Swap(int a, int b)
    {
        if (a != b)
        {
            T t = items[a];
            items[a] = items[b];
            items[b] = t;
        }
    }
}

Я оставляю вам право заменить реализацию алгоритмом по вашему выбору.

Answer 2

Я думаю, что я сделал бы это так

public static class StringPermutator
{
    /// <summary>
    /// Class to permutate input values
    /// </summary>
    /// <param name="inputValues">An array of inputs to be permutated</param>
    /// <param name="numberOfResults">The number of outputs we want to have</param>
    /// <param name="maxValuesPerRow">The number of values to be combined in each output row</param>
    /// <returns>An IEnumerable of unique permutated string ouptuts</returns>
    public static IEnumerable<string> Permutate<T>(T[] inputValues, int numberOfResults, int maxValuesPerRow)
    {
        HashSet<string> output = new HashSet<string>();
        Random rnd = new Random();

        //Loop until we have the number of results we want
        while (output.Count < numberOfResults)
        {
            StringBuilder sb = new StringBuilder();
            HashSet<int> usedIndexes = new HashSet<int>();

            //Loop until we have the right number of values in a single row
            while (usedIndexes.Count < maxValuesPerRow)
            {
                int index = rnd.Next(inputValues.Length);
                //Ensure that each index we use is unique and only used once per row
                if (usedIndexes.Add(index))
                    sb.Append(inputValues[index].ToString()).Append(",");
            }

            sb.Length--;    //remove the last comma
            output.Add(sb.ToString());   //value is only added if unique
        }

        return output.ToList();
    }
}

Вы можете назвать это так

var result = StringPermutator.Permutate(stringValues, 100, 24);

foreach (var permutation in result)
{
    Console.WriteLine(string.Join(",", permutation));
}

В основном, класс использует HashSet, который обеспечивает возможность ввода только уникальных значений, поэтому мы можем быть уверены, что наши выходные данные не дублируются, и мы просто зациклимся, пока у нас не будет нужного числа сгенерированных выходных значений.

В этом цикле мы случайным образом выбираем индекс для использования, и, чтобы гарантировать, что он также уникален для каждого выходного значения, мы снова используем HashSet для хранения используемых индексов и цикла, пока мы не скомбинируем правильное количество значений в один выходной ряд.

Возвращается список Enumerable. Это должно работать с любым типом входного значения, а не только со строками.

Edit:

Просто чтобы уточнить, согласно комментариям. Если у вас недостаточно входных данных для генерации необходимого вам количества комбинаций перестановок и строк, вы можете застрять в цикле. Таким образом, вы должны написать метод, чтобы вырваться из этого, но для простоты примера я этого не сделал.