CODEWITHSUNDEEP
c#numbers
HPT
HPT

Reputation: 351

Moderate changing of a number

Assume I have a number with 7 digits. I need a function like this

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

which returns list of all numbers that can change to input with exact number of digit changes equals to count;

for example ( the example is in 2 digit due to simplicity):

GetVariations(20, 1) should return {00,10,30,40,50,60,70,80,90,21,22,23,24,25,26,27,28,29} GetVariations(20, 2) should return {01,...,18,19,31,32,...,98,99}

This is not a homework and I've already implemented this by making all numbers and compare each of them with input and get number of changes but this approach has performance issue in numbers with bigger digits.

Upvotes: 2

Views: 106

Answers (1)

CodesInChaos
CodesInChaos

Reputation: 108850

This looks unrelated to numbers to me. You have a string and you want to create variations with a limited http://en.wikipedia.org/wiki/Hamming_distance.

It's relatively nice to implement this recursively:

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

(I didn't test the code, so it probably contains a few minor bugs)

Upvotes: 4

Related Questions