Умеренная смена номера

Question

Предположим, у меня есть номер с 7 цифрами.Мне нужна функция, подобная этой

List<int> GetVariations(int input, int count)

, которая возвращает список всех чисел, которые можно изменить для ввода с точным числом изменений цифр, равным count;

например (пример из двух цифр из-за простоты):

GetVariations(20, 1) должен вернуть {00,10,30,40,50,60,70,80,90,21,22,23,24,25,26,27,28,29} GetVariations(20, 2) должен вернуть {01, ..., 18,19,31,32, ..., 98,99}

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

Answer 1

Это выглядит не связанным с цифрами для меня.У вас есть строка, и вы хотите создать варианты с ограниченным http://en.wikipedia.org/wiki/Hamming_distance.

Относительно неплохо реализовать это рекурсивно:

IEnumerable<string> GetVariations(string input, int limit,char[] characters)
{
  if(limit==0)
  {
    yield return input;
    yield break;
  }
  if(limit>input.Length)//Disallows fewer than `limit` changes.
  {
    yield break;
  }
  string remainder=input.SubString(1);
  foreach(char c in characters)
  {
    int remainingLimit;
    if(c==input[0])
      remainingLimit=limit;
    else
      remainingLimit=limit-1;
    foreach(string variedRemainder in GetVariations(remainder,remainingLimit,characters)
      yield return c+variedRemainder;
  }
}

List<int> GetVariations(int input, int count)
{
  return GetVariations(input.ToString(),count,new char[]{'0',...,'9'}).Select(int.Parse).ToList();
}

(я не тестировал код, поэтомувероятно, содержит несколько мелких ошибок)