檢查一個字符串是否排序

Question

我有一個字符串，簡化爲"12345"它是排序的。字符串couild包含數字（0-9）或字母（a-z）。如果混合使用自然排序順序。我需要一種方法來驗證這是否屬實。

嘗試使用LINQ技術：

string items1 = "2349"; //sorted 
string items2 = "2476"; //not sorted, 6<>7 

bool sorted1 = Enumerable.SequenceEqual(items1.OrderBy(x => x), items1); //true 
bool sorted2 = Enumerable.SequenceEqual(items2.OrderBy(x => x), items2); //false 

但可能還按降序排序。

是否有更好的方法，然後

string items3 = "4321"; 
bool sorted3 = Enumerable.SequenceEqual(items3.OrderBy(x => x), items3) || Enumerable.SequenceEqual(items3.OrderByDescending(x => x), items3); 

檢查一個字符串排序？也許有些內置解決方案？

Answer 1

我曾經檢查過類似於您的案例，但數據流量很大，因此性能很重要。我想出了這個小的擴展類，它有很好的表現：

public static bool IsOrdered<T>(this IEnumerable<T> enumerable) where T: IComparable<T> 
{ 
    using (var enumerator = enumerable.GetEnumerator()) 
    { 
     if (!enumerator.MoveNext()) 
      return true; //empty enumeration is ordered 

     var left = enumerator.Current; 
     int previousUnequalComparison = 0; 

     while (enumerator.MoveNext()) 
     { 
      var right = enumerator.Current; 
      var currentComparison = left.CompareTo(right); 

      if (currentComparison != 0) 
      { 
       if (previousUnequalComparison != 0 
        && currentComparison != previousUnequalComparison) 
        return false; 

       previousUnequalComparison = currentComparison; 
       left = right; 
      } 
     } 
    } 

    return true; 
} 

使用它，顯然是非常簡單的：

var items1 = "2349"; 
var items2 = "2476"; //not sorted, 6<>7 
items1.IsOrdered(); //true 
items2.IsOrdered(); //false 

Answer 2

var items = "4321"; 
var sortedItems = items.OrderBy(i => i); // Process the order once only 
var sorted = sortedItems.SequenceEqual(items) || sortedItems.SequenceEqual(items.Reverse()); // Reverse using yield return 

Answer 3

您的解決方案精細且非常易讀。其中一個問題是，它需要訂購stringwhich is O(n * log(n))，這可以通過迭代string而不對其進行排序來解決。

例如：

var firstDifs = items1.Zip(items1.Skip(1), (x, y) => y - x); 

這Linq項目每2項第一string了一些這表明它們的區別，所以，如果你有items1 = "1245"輸出將是：

firstDifs： {1, 2, 1}

現在您所需要做的就是驗證德那firstDifs是按升序或降序：

bool firstSorted = firstDifs.All(x => x > 0) || firstDifs.All(x => x < 0); //true 

目前：

• Skip是O（1）由於跳過1個細胞所需的動作量是 恆定。
• Zip是O（n）。
• All是O（n）。

所以整個溶液爲爲O（n）。

注意這將是更有效的用一個簡單的循環，還當第一All返回false因爲第三千四百八十七項目改變其方向（例如：1234567891），第二All會無緣無故跑Zip運行兩次以上_{（直到All要求）} - 因爲有兩個迭代All和Linq懶惰地評估它們。

Answer 4

我會去簡單迭代所有元素：

string str = "whatever123"; 
Func<char, char, bool> pred; 
bool? asc = str.TakeWhile((q, i) => i < str.Length - 1) 
       .Select((q, i) => str[i] == str[i+1] ? (bool?)null : str[i] < str[i+1]) 
       .FirstOrDefault(q => q.HasValue); 
if (!asc.HasValue) 
    return true; //all chars are the same 
if (asc.Value) 
    pred = (c1, c2) => c1 <= c2; 
else 
    pred = (c1, c2) => c1 >= c2; 

for (int i = 0; i < str.Length - 1; ++i) 
{ 
    if (!pred(str[i], str[i + 1])) 
     return false; 
} 
return true; 

Answer 5

它需要一個reducer。在C＃中，它是Enumerable.Aggregate。這是O（n）算法。

var query = "123abc".Aggregate(new { asceding = true, descending = true, prev = (char?)null }, 
(result, currentChar) => 
    new 
    { 
     asceding = result.prev == null || result.asceding && currentChar >= result.prev, 
     descending = result.prev == null || result.descending && currentChar <= result.prev, 
     prev = (char?)currentChar 
    } 
); 
Console.WriteLine(query.asceding || query.descending); 

Answer 6

您可以不必比較所有的做多接受的答案要好得多的元素：

var s = "2349"; 
var r = Enumerable.Range(1, s.Length - 1); 
//var isAscending = r.All(i => s[i - 1] <= s[i]); 
//var isDescending = r.All(i => s[i - 1] >= s[i]); 
var isOrdered = r.All(i => s[i - 1] <= s[i]) || r.All(i => s[i - 1] >= s[i]);