C#练习题答案: 字母字谜【难度：5级】

字谜【难度：5级】"/>

C#练习题答案: 字母字谜【难度：5级】

字母字谜【难度:5级】:

答案1:

using System;
using System.Collections.Generic;
using System.Linq;public class Kata
{public static long ListPosition(string value){long rank = 1;long suffixPermCount = 1;var charCounts = new Dictionary<char, int>();for (var i = value.Length - 1; i > -1; i--){var current = value.ElementAt(i);var currentCount = charCounts.ContainsKey(current) ? charCounts[current] + 1 : 1;if (charCounts.ContainsKey(current)){charCounts[current] = currentCount;}else{charCounts.Add(current, currentCount);}rank += charCounts.Where(charCount => charCount.Key < current).Sum(charCount => suffixPermCount*charCount.Value/currentCount);suffixPermCount *= value.Length - i;suffixPermCount /= currentCount;}return rank;}
}​

答案2:

using System.Collections.Generic;
using System.Linq;struct Range
{public long LowBound;public long HighBound;
}public static class Kata
{static long GetNumberOfPermutationsWithRepetition(this string value, SortedDictionary<char, int> countByLetter){long result = Factorial(value.Length);foreach (int Ni in countByLetter.Values)result /= Factorial(Ni);return result;}static long Factorial(int x){long factorial = 1;for (int i = 1; i <= x; i++)factorial *= i;return factorial;}static long GetListPosition(this string value, Range range, SortedDictionary<char, int> countByLetter){if (range.LowBound == range.HighBound)return range.LowBound;long numberOfPermutationsWithRepetition = value.GetNumberOfPermutationsWithRepetition(countByLetter);long step = numberOfPermutationsWithRepetition / value.Length;long lowBoundIncrement = 0;foreach (char letter in countByLetter.Keys){if (letter == value[0])break;lowBoundIncrement += step * countByLetter[letter];}long highBoundDecrement = numberOfPermutationsWithRepetition - (lowBoundIncrement + step * countByLetter[value[0]]);Range newRange;newRange.LowBound = range.LowBound + lowBoundIncrement;newRange.HighBound = range.HighBound - highBoundDecrement;countByLetter[value[0]]--;return value.Substring(1).GetListPosition(newRange, countByLetter);}public static long ListPosition(string value){SortedDictionary<char, int> countByLetter = new SortedDictionary<char, int>();foreach (char letter in value.Distinct())countByLetter.Add(letter, value.Count(c => c == letter));Range range;range.LowBound = 1;range.HighBound = value.GetNumberOfPermutationsWithRepetition(countByLetter);return value.GetListPosition(range, countByLetter);}
}​

答案3:

using System;
using System.Linq;
using System.Collections.Generic;public class Kata
{public static long ListPosition(string value){var chars = new List<char>(value.OrderBy(c => c));return value.Aggregate(1L, (pos,cur) =>{var before = chars.TakeWhile(c => c != cur).Count();var adjust = chars.GroupBy(c => c).Aggregate(1L, (p,g) => p * Fac(g.Count()));chars.Remove(cur);return pos + before * Math.Max(1L, Fac(chars.Count)) / adjust;});}private static long Fac(long i) => i < 2 ? i : i * Fac(i - 1);
}​

答案4:

using System;
using System.Collections.Generic;
using System.Linq;public class Kata
{public static long ListPosition(string word){long index = 1;string sortedWord = string.Concat(word.OrderBy(c => c).Distinct());var charCounts = new Dictionary<char, long>();foreach (char c in word){if (charCounts.ContainsKey(c)) charCounts[c]++;else charCounts.Add(c, 1);}for (int i = 0; i < word.Length - 1; i++){int j = -1;while (sortedWord[++j] != word[i]){charCounts[sortedWord[j]]--;long top = Factorial(word.Length - 1 - i);long bottom = charCounts.Aggregate(1, (long x, KeyValuePair<char, long> y) => x * Factorial(y.Value));index += top / bottom; //using a combinatorics formulacharCounts[sortedWord[j]]++;}charCounts[word[i]]--;if (charCounts[word[i]] == 0){charCounts.Remove(word[i]);sortedWord = sortedWord.Remove(sortedWord.IndexOf(word[i]), 1);}}return index;}static long Factorial(long n){long f = 1;while (n > 1) f *= n--;return f;}
}​

答案5:

using System.Collections.Generic;public class Kata
{public static long ListPosition(string value){long position = 1;long factorial = 1;long duplicateFactorials = 1;var charCounts = new Dictionary<char, int> { { value[value.Length - 1], 1 } };for (int i = value.Length - 2; i >= 0; --i){char c = value[i];int lowerCharCount = 0;for (int j = i + 1; j < value.Length; ++j)lowerCharCount += (value[j] < c ? 1 : 0);charCounts[c] = (charCounts.ContainsKey(c) ? charCounts[c] : 0) + 1;duplicateFactorials *= charCounts[c];position += lowerCharCount * (factorial / duplicateFactorials);factorial *= value.Length - i;}return position;}
}​

答案6:

using System.Collections.Generic;
using System.Linq;public static class Kata
{static long GetNumberOfPermutationsWithRepetition(this string value, SortedDictionary<char, int> countByLetter){long result = Factorial(value.Length);foreach (int Ni in countByLetter.Values)result /= Factorial(Ni);return result;}static long Factorial(int x){long factorial = 1;for (int i = 1; i <= x; i++)factorial *= i;return factorial;}public static long ListPosition(string value){SortedDictionary<char, int> countByLetter = new SortedDictionary<char, int>();foreach (char letter in value.Distinct())countByLetter.Add(letter, value.Count(c => c == letter));long lowBound = 1;long highBound = value.GetNumberOfPermutationsWithRepetition(countByLetter);while (lowBound != highBound){long numberOfPermutationsWithRepetition = value.GetNumberOfPermutationsWithRepetition(countByLetter);long step = numberOfPermutationsWithRepetition / value.Length;long lowBoundIncrement = 0;foreach (char letter in countByLetter.Keys){if (letter == value[0])break;lowBoundIncrement += step * countByLetter[letter];}long highBoundDecrement = numberOfPermutationsWithRepetition - (lowBoundIncrement + step * countByLetter[value[0]]);lowBound = lowBound + lowBoundIncrement;highBound = highBound - highBoundDecrement;countByLetter[value[0]]--;value = value.Substring(1);}return lowBound;}
}​

答案7:

using System.Collections.Generic;
using System;public class Kata
{public static long ListPosition(string word){Dictionary<char,long> letters = new Dictionary<char,long>();long holder = 0;long result = 1;for(int i = 0; i < word.Length; i++){  if(letters.TryGetValue(word[i], out holder))letters[word[i]] += 1;elseletters.Add(word[i],1);}for(int i = 0; i < word.Length; i++){foreach(var x in letters){if(x.Value != 0 &amp;&amp; x.Key < word[i]){long division = 1;foreach(var c in letters){if (c.Key == x.Key)division *= factorial(c.Value - 1);elsedivision *= factorial(c.Value);}result += Kata.factorial(word.Length - i - 1)/division;}}letters[word[i]] -= 1;}return result;}private static long factorial(long n){long result = 1;while(n > 1){result *= n;n -= 1;}return result;}
}​

答案8:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;public class Kata
{public static long ListPosition(string value){var array = value.ToCharArray();var sorted = array.OrderBy(c => c).ToArray();var position = 1L;var unique = sorted.GroupBy(c => c).Select(cc => cc.Key).ToArray();int i = 0, j = 0;while (i < array.Length || j < unique.Length){if (array[i] == unique[j++]){var tmp = sorted.ToList();tmp.Remove(array[i]);sorted = tmp.ToArray();unique = sorted.GroupBy(c => c).Select(cc => cc.Key).ToArray();i++;j = 0;}else{var _sorted = sorted.ToList();_sorted.Remove(array[i] < unique[j - 1] ? array[i] : unique[j - 1]);var c = CountAnagrams(_sorted.ToArray());position += c;}}return position;}private static long F(int n){return n == 0 ? 1 : F(n - 1) * n;}private static long CountAnagrams(char[] word){var groupsCount = word.GroupBy(c => c).Select(cc => cc.Count()).ToList();var numerator = F(word.Length);var denominator = groupsCount.Aggregate<int, long>(1, (current, t) => current * F(t));return numerator / denominator;}    
}​

答案9:

using System;
using System.Collections.Generic;
using System.Linq;public class Kata
{public static long ListPosition(string value){List<char> charList = value.ToCharArray().ToList();List<long> result = new List<long>();int counter = value.Length - 2;for (int i = 0; i <= counter; i++){List<char> freeCharList = charList.Skip(i+1).ToList();List<char> freeCharListAndI = new List<char>(freeCharList) {charList[i]};List<char> distinctfreeList = new List<char>(freeCharList.Distinct().ToList());foreach (char c in distinctfreeList){List<char> myFreeCharList = new List<char>(freeCharListAndI);if (charList[i] > c){myFreeCharList.Remove(c);long nominator = Enumerable.Range(1, myFreeCharList.Count).Select(p=>long.Parse(p.ToString())).Aggregate((a, b) => a*b);long denominator = myFreeCharList.GroupBy(p => p).Select(p => p.Count()).Select(p => Enumerable.Range(1, p).Select(v => long.Parse(v.ToString())).Aggregate((a, b) => a * b)).Aggregate((a, b) => a*b);result.Add(nominator/denominator);}}}return result.Sum() + 1;}
}​

答案10:

using System;
using System.Linq;public class Kata
{public static long ListPosition(string value){var ordered = value.Select(x=>x).OrderBy(x => x).ToList();var length = value.Length;var pos = 0L;while(length > 0){length--;var caract = value[value.Length -1 - length];var indi= ordered.IndexOf(caract);var nbMots = Factoriel(length) * indi;ordered.GroupBy(x => x).Select(x => (long)x.Count()).ToList().ForEach(x => nbMots /= Factoriel(x));pos += nbMots;ordered.Remove(caract);}pos ++;return long.Parse(pos.ToString());} static long Factoriel(long n)  { return n > 1?n * Factoriel(n-1):1; }  }​