Implementation of the conversion of the elements of sheet C# (similar to next_permutation from STL)



  • Hello! The challenge is to perform a function that generates all possible changes in the List site. If all the alterations are over, we should start in circle one. The search on the Internet didn't make a decision. Resources reviewed:

    https://stackoverflow.com/questions/2390954/how-would-you-calculate-all-possible-permutations-of-0-through-n-iteratively/12768718#12768718
    https://stackoverflow.com/questions/11208446/generating-permutations-of-a-set-most-efficiently
    http://olsen.org/alan/blog/?p=85

    One of the references was tested:

    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 &gt; 0; i--)
        {
            var curr = elements[i];
    
            // Check if the current element is less than the one before it
            if (curr.CompareTo(elements[i - 1]) &lt; 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 &lt; 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) &lt; 0 &amp;&amp; tmp.CompareTo(prev) &gt; 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 &gt; 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;
    }
    

    The founcture is such:

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

    However, the compiler makes a mistake:

    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>>'.

    Is this linked to the need for a user comparator for couples to perform?
    Maybe there's a solution somewhere, and I just don't see it?



  • Your method requires an element to provide an interface. IComparable<T>KeyValuePair This interface doesn't work.

    Use it. https://msdn.microsoft.com/en-us/library/dd268536(v=vs.110).aspx instead KeyValuePair and substitute where T : IComparable<T>where T : IComparable

    Better, finish the function so she can take the second parameter. IComparer<T>and replace challenges x.CompareTo(y)comparer.Compare(x, y)




Suggested Topics

  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2