1

Здравствуйте! Есть задача - реализовать функцию, которая генерирует все возможные перестановки в объекте List. Если все перестановки закончились, следует начинать по кругу с первой. Поиск в интернете не дал искомого решения. Просмотренные ресурсы:

How would you calculate all possible permutations of 0 through N iteratively?
Generating permutations of a set (most efficiently)
C# (C sharp) next_permutation function

Был опробован вот такой код, найденный по одной из ссылок:

private static bool NextPermutation<T>(List<T> elements) where T : IComparable<T>
    {
        // More efficient to have a variable instead of accessing a property
        var count = elements.Count;

        // Indicates whether this is the last lexicographic permutation
        var done = true;

        // Go through the array from last to first
        for (var i = count - 1; i > 0; i--)
        {
            var curr = elements[i];

            // Check if the current element is less than the one before it
            if (curr.CompareTo(elements[i - 1]) < 0)
            {
                continue;
            }

            // An element bigger than the one before it has been found,
            // so this isn't the last lexicographic permutation.
            done = false;

            // Save the previous (bigger) element in a variable for more efficiency.
            var prev = elements[i - 1];

            // Have a variable to hold the index of the element to swap
            // with the previous element (the to-swap element would be
            // the smallest element that comes after the previous element
            // and is bigger than the previous element), initializing it
            // as the current index of the current item (curr).
            var currIndex = i;

            // Go through the array from the element after the current one to last
            for (var j = i + 1; j < count; j++)
            {
                // Save into variable for more efficiency
                var tmp = elements[j];

                // Check if tmp suits the "next swap" conditions:
                // Smallest, but bigger than the "prev" element
                if (tmp.CompareTo(curr) < 0 && tmp.CompareTo(prev) > 0)
                {
                    curr = tmp;
                    currIndex = j;
                }
            }

            // Swap the "prev" with the new "curr" (the swap-with element)
            elements[currIndex] = prev;
            elements[i - 1] = curr;

            // Reverse the order of the tail, in order to reset it's lexicographic order
            for (var j = count - 1; j > i; j--, i++)
            {
                var tmp = elements[j];
                elements[j] = elements[i];
                elements[i] = tmp;
            }

            // Break since we have got the next permutation
            // The reason to have all the logic inside the loop is
            // to prevent the need of an extra variable indicating "i" when
            // the next needed swap is found (moving "i" outside the loop is a
            // bad practice, and isn't very readable, so I preferred not doing
            // that as well).
            break;
        }

        // Return whether this has been the last lexicographic permutation.
        return done;
    }

Функцию вызываю так:

List<KeyValuePair<string, string>> src = new List<KeyValuePair<string, string>>();
src.Add(new KeyValuePair<string, string>("fruit", "orange"));
src.Add(new KeyValuePair<string, string>("vegetable", "cabbage"));
src.Add(new KeyValuePair<string, string>("animal", "dog"));
bool rez = NextPermutation(src);

Однако, компилятор выдаёт ошибку:

The type 'System.Collections.Generic.KeyValuePair<string,string>' cannot be used as type parameter 'T' in the generic type or method 'NextPermutation<T>(System.Collections.Generic.List<T>)'. There is no boxing conversion from 'System.Collections.Generic.KeyValuePair<string,string>' to 'System.IComparable<System.Collections.Generic.KeyValuePair<string,string>>'.

Связано ли это с тем, что нужно реализовывать пользовательский компаратор для пар ключ-значение? Может где-то уже есть решение, и я просто его не вижу?

1 ответ 1

1

Ваш метод требует, чтобы элемент предоставлял интерфейс IComparable<T>. KeyValuePair этот интерфейс не реализует.

Используйте Tuple<string, string> вместо KeyValuePair и замените ограничение where T : IComparable<T> на where T : IComparable.

А лучше - допишите функцию так, чтобы она вторым параметром принимала IComparer<T>, и замените вызовы x.CompareTo(y) на comparer.Compare(x, y).

2
  • теперь другие ошибки посыпались... Например, что функция CompareTo() из приведённого выше кода - приватна и не может быть доступна из моей функции...
    – neo
    10 дек 2015 в 11:57
  • @neo скорее всего в сообщении об ошибке было сказано совсем не то. подправил ответ.
    – user177221
    10 дек 2015 в 12:03

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.