Найти а[i+1]—наименьшее число больше a[i], в котором нет цифр из a[i]

#алгоритм #числовые_последовательности

Числовая последовательность {an} строится следующим образом: a0 = 1, для любого i
≥ 0 число ai+1, больше ai, равно наименьшему натуральному числу, в десятичном представлении
которого нет десятичных цифр ai. По номеру i вывести ai.

Так будет выглядеть последовательность:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 22, 30, 41, 50, 61, 70, 81, 90, 111, 200, 311, 400,
511, 600, 711, 800, 911, 2000, 3111, 4000, 5111, 6000, 7111, 8000, 9111, 20000, 31111,
40000, 51111, 60000, 71111, 80000, 91111, 200000...

Как реализовать это? Или хотя бы основной принцип подскажите,
мучаюсь уже 3 дня, а сдавать завтра
    

Ответы

Ответ 1

Напишите метод, который вернет следующий элемент последовательности по предыдущему:

static int Next(int current)
{
    // Запоминаем все цифры, которые есть в текущем числе
    var digits = current.ToString().Distinct().ToList();
    // Увеличиваем число на 1 до тех пор, пока в новом числе встречаются цифры из
входного
    while ((++current).ToString().Distinct().Intersect(digits).Any());
    // Пересечений по цифрам нет, возвращаем результат
    return current;
}


Остается только вызвать его нужное количество раз:

int n = 20;
int a = 1;
for (int i = 1; i <= n; ++i) a = Next(a);
Console.WriteLine(a);




Если требуется вычислять a для больших индексов, то можно придумать решение O(1)
(верно?). Как заметил в комментариях @AnT, в последовательности есть "стабильные" участки,
можно этим воспользоваться так:

static string GetA(int index)
{
    if (index <= 9) return (index + 1).ToString();
    if (index == 10) return "22";
    if (index <= 17) return (index - 8).ToString() + ((index - 1) % 2).ToString();
    if (index == 18) return "111";
    return ((index - 3) % 8 + 2).ToString() + new string((char)((index - 1) % 2 +
'0'), (index - 3) / 8);
}


Например, GetA(4321) вычисляется мгновенно и возвращает:


  800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000


Ответ 2

Начало последовательности - до 200 - можно сохранить в явном виде. А с 200 и далее
последовательность ведет себя периодично-предсказуемо: первая цифра равна (i - 3) %
8 + 2, а за ней следует либо (i - 3) / 8 нулей (для нечетных i), либо столько же единиц
(для четных i)

#include 

unsigned long long ai(unsigned i)
{
  static const unsigned long long prefix[] = 
    { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 22, 30, 41, 50, 61, 70, 81, 90, 111 };

  if (i < 19)
    return prefix[i];

  i -= 3;

  unsigned long long v = i % 8 + 2;
  for (unsigned p = i / 8; p > 0; --p)
    v = v * 10 + i % 2;

  return v;
}

int main()
{
  for (unsigned i = 0; i < 100; ++i)
    std::cout << ai(i) << std::endl;
}


Ответ 3

function next(/* string */ s) {
  // преобразовать строку в массив
  var a = [...s]

  // отметить использованные символы в словаре
  var used = Object.create(null)
  for (var ch of a) used[ch] = true
  
  // найти минимальный свободный символ
  var ch = 0
  for (ch = 0; ch <= 9; ++ch)
    if (!used[ch])
      break
  
  // Попробовать увеличить первый символ
  if (++a[0] == 10) {
    // если не вышло, добавляем ещё один в начало
    a.unshift(ch)
    
    // лидирующих нулей быть не должно, ищем следующий символ, если добавили 0
    if (ch == 0)
      while (++a[0]<=9)
        if (!used[a[0]])
          break
  }
  
  // все остальные символы заменяем на минимальный
  for (var q=1; q