c# - 适度改变号码

Question

假设我有一个 7 位数字的号码。 我需要这样的功能

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

返回可以更改为输入的所有数字的列表，其中数字更改的确切数量等于 count ;

例如(为了简单起见，示例采用 2 位数字):

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

(我没有测试代码，所以它可能包含一些小错误)