Последовательность Seqindignot

27

Заголовок составлен из «Номера индекса последовательности не».

Вызов:

Дано целое число , nкоторое >= 0, выведите n«й номер следующей последовательности.
Вот первые 50 элементов с индексом (0-index) над ним:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
1 0 3 2 5 4 7 6 9 8 22 20 30 24 23 26 25 28 27 32 11 33 10 14 13 16 15 18 17 31 12 29 19 21 50 40 41 42 44 45 35 36 37 51 38 39 52 53 55 56 34

Как работает эта последовательность?

Число в индексе nдолжно быть первым, чтобы не иметь общих цифр с n, и еще не встречалось для предыдущих индексов. Итак, когда мы посмотрим на нормальную последовательность, как это из 0-60:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

Мы определяем n'-ые значения следующим образом:

  • 0: Первое число ( 0) содержит ту же цифру, поэтому мы ищем следующее ( 1), которое не содержит той же цифры. Итак, n=0выводы 1.
  • 1: Первое число ( 0) не содержит одинаковую цифру, поэтому n=1выводится 0.
  • 2: Мы уже встречали 0и 1, и следующая цифра ( 2) содержит ту же цифру, поэтому мы ищем следующую ( 3), которая не содержит той же цифры. Итак, n=2выводы 3.
  • ...
  • 10: Мы уже встречались 0-9, поэтому следующий в очереди 10. 10-19содержит совпадающую цифру 1, 20содержит совпадающую цифру 0, снова 21содержит совпадающую цифру 1, 22является действительным, поэтому n=10выводит 22.
  • и т.п.

Правила соревнований:

  • Если ваш язык индексируется 1 (или вы выбираете), вы можете начать последовательность с 3 2 5 4 7 ...(пропуская 1at n=0и 0at n=1).
  • Минимальный наибольший индекс, который вы должны поддерживать, это 25,000. ПРИМЕЧАНИЕ. Последовательность заканчивается индексом 1,023,456,788, поскольку следующий индекс в строке содержит все 10 цифр.
  • Вы также можете выводить / возвращать массив / список всей последовательности вплоть до индекса, nесли хотите.

Основные правила:

  • Это код-гольф , поэтому выигрывает самый короткий ответ в байтах.
    Не позволяйте языкам кода-гольфа отговаривать вас от публикации ответов на языках, не относящихся к кодексу. Попробуйте придумать как можно более короткий ответ для «любого» языка программирования.
  • К вашему ответу применяются стандартные правила , поэтому вы можете использовать STDIN / STDOUT, функции / метод с правильными параметрами и типом возврата, полные программы. Ваш звонок.
  • По умолчанию лазейки запрещены.
  • Если возможно, добавьте ссылку с тестом для вашего кода.
  • Также, пожалуйста, добавьте объяснение, если это необходимо.

Тестовые случаи:

Эта последовательность фактически создала пары относительно индекса и выходов. Если индекс nвыводит o, индекс oвыводит n. Таким образом, вы можете ввести либо левую, либо правую, и вывод будет с другой стороны:

0      <->  1       (this test case is optional)
2      <->  3
10     <->  22
12     <->  30
34     <->  50
89     <->  100
111    <->  200
112    <->  300
199    <->  322
2231   <->  4456
9605   <->  11118
19235  <->  46000
23451  <->  60668
25000  <->  13674

Вот пастбин из первых 25 001 контрольных примеров, если вы хотите попробовать другие.

code-golf number sequence integer Кевин Круйссен
источник
Связанный, но не дурак.
Кевин Круйссен
3
Как и в случае с сопутствующей задачей, график рассеяния довольно забавный . :)
Мартин Эндер
@MartinEnder Когда я увидел график рассеяния связанной задачи, я действительно подумал, что это будет похоже. Оказывается, это действительно довольно похоже, но все же отличается. :)
Кевин Круйссен
Почему такая важная последовательность не на OEIS?
Стьюи Гриффин
@StewieGriffin Хороший вопрос. На самом деле, я думаю, что все мои проблемы с последовательностями до сих пор не были в OEIS (пока), когда я их опубликовал. ;)
Кевин Круйссен

Ответы:

3

Pyth , 18 байт

u+Gf!|}TG@`H`T0hQY

Попробуй это здесь! или проверьте больше тестовых случаев!

Обратите внимание, что это возвращает всю последовательность вплоть до индекса N , но ссылка возвращает только последнее число, добавляя e(конец). Если вы хотите увидеть необработанное значение, возвращаемое этой программой, просто удалите его .

Как это работает

u + Gf! |} TG @ `H`T0hQY - Полная программа.

u ... hQY - Уменьшить hQ (приращение) слева направо, с помощью
                       функция ... (G, H), с начальным значением Y (пустой список).
                       G - текущее значение, а H - индекс итерации.
   f 0 - первое целое число, начинающееся с 0, удовлетворяющее следующему:
      } TG - появляется в G ...
     | @ `H`T - или его (строка) пересечение с текущим индексом (H)
                        не пусто.
    ! - Логическое НЕ (логическое отрицание).
 + G - Добавить полученное выше значение к текущему значению (G).
                      Это становится заданным значением для следующей итерации.
                    - Неявная печать всех промежуточных результатов или добавление e для печати 
                      последний.
Мистер Xcoder
источник
6

Python 2 , 92 91 89 88 байт

a=()
i=0
exec"x=0\nwhile set(`x`)&set(`i`)or x in a:x+=1\na+=x,;i+=1;"*-~input()
print a

Попробуйте онлайн!

Распечатывает список первых n+1чисел

Другой подход, который намного быстрее:

Python 2 , 96 байт

n=input()
r=range(9*n)
i=0
exec"x=0\nwhile set(`r[x]`)&set(`i`):x+=1\nprint r.pop(x),;i+=1;"*-~n

Попробуйте онлайн!

TFeld
источник
1
88 байтов с использованием кортежа
Mr. Xcoder
3

Haskell, 80 69 байтов

f n=[x|x<-[0..],all(`notElem`show n)$show x,all(/=x)$f<$>[0..n-1]]!!0

Попробуйте онлайн!

Очень медленно для большого n.

f n=
    [x|x<-[0..]     ] !!0          -- pick the first of all 'x' from [0..]
                                   -- where
      all(`notElem`show n)$show x  -- no digit of 'n' appears in 'x', and
      all(/=x)                     -- 'x' is not seen before, i.e. not in the list
               f<$>[0..n-1]        -- 'f' mapped to [0..n-1]

Изменить: @Laikoni сэкономил 10 байтов. Благодарность!

Ними
источник
Вычисление n-го члена напрямую вместо индексации в последовательности короче: попробуйте онлайн!
Лайкони
2

APL (Дьялог) , 39 байт

0∘{0=⍵:1⋄(~⍺∊0∇¨⍳⍵)∧⊃∧/≠/⍕¨⍺⍵:⍺⋄⍵∇⍨⍺+1}

Использует ⎕IO←0.

Попробуйте онлайн!

Как?

Рекурсия.

0=⍵:1 - сделать предположение.

~⍺∊0∇¨⍳⍵ - левый арг (аккумулятор) уже не в предыдущих результатах

∧⊃∧/≠/⍕¨⍺⍵- и строковое представление аккумулятора и nразные

:⍺ - затем верните аккумулятор.

⍵∇⍨⍺+1 - в противном случае увеличьте накопитель и восстановите.

Уриэль
источник
Ух ты ... Я знаю, что по умолчанию используется правило "дано любое количество памяти и времени", но ваш код уже n=10истек в TIO ..: S Это должно быть очень трудоемкой операцией, которую вы там выполняете. Это рекурсия вызывает это или что-то еще является узким местом?
Кевин Круйссен
2
@KevinCruijssen Второе условие в основном применяет функцию в диапазоне 0..n-1, и, учитывая то же самое, применяется для каждого вызова, который примерно равен огромному O (2 ^ n). конечно, было бы меньше с более разумным кодом, но вот где узкое место
Уриэль
2

Java (OpenJDK 8) , 218 217 213 210 202 200 172 171 170 168 167 байт

Я не могу поверить, что я не просто вернулся kвсе это время ...

i->{int j=-1,k=0,y=1;for(String r=" ",e=r;j++<i;r+=~-k+e,y=1)for(k=0;y>0;k++)for(int f:(k+(y=0)+"").getBytes())y+=(e+j).indexOf(f)<0&!r.contains(e+k+e)?0:1;return~-k;}

Попробуйте онлайн!

Роберто Грэм
источник
Хм, это совсем другой подход, чем тот, который я использовал, когда делал пастин с моей Java-программой. И кажется , что вы можете играть в гольф , for(char f:(""+k).toCharArray())чтобы for(int f:(""+k).getBytes()), r.substring(-~r.trim().lastIndexOf(32));и r.substring(r.lastIndexOf(32)-1).
Кевин Круйссен,
Должен быть обрезан до lastIndexOf, так как в конце есть пробел
Роберто Грэхем
Ах, я действительно допустил ошибку ... Я знал, что строка содержит как начальные, так и конечные пробелы, но мои неправильно предложенные изменения работают только для первых 10 однозначных чисел. Мой плохой
Кевин Круйссен
2

Go , 217 205 байт

package g;import("fmt";"strconv";"strings");var(
d=make(map[int]int)
a=strconv.Itoa)
func G(L int){k,i:=0,0;for;i<=L;i++{s:=a(i);k=0;for d[k]>0||strings.ContainsAny(a(k),s){k++;}
d[k]=1;}
fmt.Print(a(k));}

Альтернативная версия (программа вместо пакета): попробуйте онлайн!

Улучшения:

  • убрал пробел после внешнего for, используя множественное присваивание дляi,k
  • import "fmt";+ fmt.Printкороче os.Stdout.WriteString(удержание с package mainмомента, когда был нужен os.Args)
Riking
источник
Хорошо, ваш ответ - первый, который не истекает через 1 минуту, когда я пробую 25000контрольный пример. :) Так что не только правильное решение, но и с относительно хорошими характеристиками. +1 от меня! (PS: В вашей TIO-ссылке это аргумент, который вы используете, ввод можно удалить / не использовать.)
Кевин Круйссен,
2

JavaScript (ES6), 103 88 81

Редактировать Пересмотрено, включая много умных идей @Neil

n=>eval("for(r=[j=i=0];i<=n;)j=r[j]||(i+'').match(`[${j}]`)?j+1:!(r[k=j]=++i);k")

Отправная точка

Основная идея: цикл от 0 до n, а внутренний цикл проверки значений все еще не используется

n=>{
  var r=[]
  for(i=0;i<=n;i++)
  {
    s=new Set(i+'')
    for(j=-1;s;)
    {
      if (!r[++j] && ![...j+''].some(d=>s.has(d)))
      {
        r[j]=1
        console.log(i,j)
        s=0
      }
    }
  }
  return j
}

Текущая версия более читабельна

n=>{
  for(r = [j=i=0]; i <= n; )
    if (r[j] || (i+'').match(`[${j}]`))
      ++j
    else
      r [k=j] = ++i,
      j = 0;
  return k
}

Тест

var f=
n=>eval("for(r=[j=i=0];i<=n;)j=r[j]||(i+'').match(`[${j}]`)?j+1:!(r[k=j]=++i);k")

update=_=>{
  var i=+I.value
  if (i < 1e4 || confirm("Really?")) {
    O.textContent=i + ' -> ...'
    setTimeout(_=>O.textContent=i + ' -> ' + f(i), 100)
  }
}  

update()
<input id=I value=100 type=number max=1023456788>
<button onclick='update()'>Go</button>
(slow when input > 1000)
<pre id=O></pre>
Развернуть фрагмент

edc65
источник
Будет ли замена ~s.search(d)с s.match(d)работой?
Нил
Я думаю, что вы можете сохранить еще один байт, изменив 0его j++, удалив ++из jнего, который был раньше, а затем начав jс 0вместо -1.
Нил
Я думаю, что я смог переключиться на один цикл:n=>eval("for(r=[j=i='0'];i<=n;)r[j]|[...''+j].some(d=>i.match(d))?j++:(i=++i+'',r[k=j]=1,j=0);k")
Нейл
@ Не было бы замечательно ни одной петли
edc65
@ Нейл, отличный цикл, спасибо
edc65
2

Октава , 114 байт

N=input("");o=[1];for i=1:N;j=0;while(any(o==j)||nnz(ismember(int2str(i),int2str(j))));j++;end;o=[o,j];end;[0:N;o]

Попробуйте онлайн!

Спасибо Кевину Круйссену и Длоску за сравнение характера игры в гольф.

Ungolfed

N=input("");o=[1];

for i=1:N;
    j=0;
    while(any(o==j)||nnz(ismember(int2str(i),int2str(j))));
        j++;
    end;
    o=[o,j];
end;
[0:N;o]

Основное объяснение:

  • Внешний цикл и внутренний цикл, один для индекса i, а другой для значения, чтобы добавитьj

  • Для каждого iпродолжайте увеличивать, jесли выполняется одно из следующих:

    1. Любой jбыл использован раньше
    2. Этот получает удовольствие. Сначала разбейте каждое числовое значение на вектор цифр (например, 10становится [1 0]), используя int2str. Затем сравните два числа с помощью ismember(например, [1 0]и [2 1]вернул бы [1 0]), а затем nnzпосмотрите, совпадают ли какие-либо столбцы.

  • Если ничего из перечисленного не выполнено, у вас есть следующий номер! Добавить к oвыходной матрице

  • Печать оригинальных индексов с выходной матрицей
Алан
источник
Хороший ответ, +1 от меня. И, похоже, @DLosc прав, он работает даже без того и другого -'0'. Но если есть какой-то крайний случай, о котором мы оба не подумали, -48будет более короткая альтернатива. Также оба sprintf('%d',...)могут быть int2str(...).
Кевин Круйссен
1

Perl 5 , 60 байт

59 байт код + 1 для -p.

$_="@{[0..($;=++$_)*9]}";$_=eval's/\b[^ $-]+ //;$-++;$&;'x$

Попробуйте онлайн! (Включает -lдля визуальных целей и $-=0;для сброса каждой итерации)

Дом Гастингс
источник
1

Пип , 30 байт

29 байт кода, +1 для -p флага.

Fn,a+1{Y0WyNl|_NyMSn++ylPBy}l

Попробуйте онлайн!

Выводит весь список. Предупреждение: крайне неэффективно; 2231на моем ноутбуке ввода продолжался более 35 минут и до сих пор не завершен.

объяснение

                               a is cmdline arg, l is [] (implicit)
Fn,a+1{                    }   For each n in range(a+1):
       Y0                       Yank 0 into y
         W                      While...
          yNl|                  y is in l, or...
              _Ny               lambda function: arg is in y
                 MSn            mapped to digits of n and result list summed
                                (i.e., any digit of n is in y):
                    ++y          Increment y
                       lPBy     Once we have a y that meets the criteria, push it to
                                the back of l
                            l  Output l (formatted with -p flag)
DLosc
источник
1

Visual Basic .NET (.NET 4.5) , 260 259 байт

-1 байт благодаря Кевину Круйссену

Function A(n)
Dim p=New System.Collections.Generic.List(Of Long),j="0",g=0
For i=0To n
j=0
While 1
If Not p.Contains(j)Then
g=1
For Each c In i.ToString
If j.Contains(c)Then g=0
Next
If g Then Exit While
End If
j+=1
End While
p.Add(j)
Next
A=p(n)
End Function

Перебирает, генерируя предыдущие термины в последовательности, чтобы потом сравнивать позже. Затем повторяет число в виде строки, ища совпадения.

Злоупотребление системой ввода VB.NET. Например, jэто строка, но добавление одной конвертирует в целое число для меня. Целые преобразуются в булевы , где 0находитсяFalse а остальные True.

Попробуйте онлайн!

Брайан Дж
источник
Я никогда не программировал в Visual Basic, но кажется, что вы можете удалить пробел так If Not p.Contains(j)Thenже, как вы это сделали If j.Contains(c)Then g=0ниже. Кроме того, If Not p.Contains(j)Then \n g=1 \n For Each c In i.ToString \n If j.Contains(c)Then g=0 \n Next \n If g Then Exit While \n End Ifможет быть сокращен путем удаления gи использования Exit Whileнепосредственно в цикле for:, If Not p.Contains(j)Then \n For Each c In i.ToString \n If j.Contains(c)Then Exit While \n Next \n End Ifкоторый, по внешнему виду, станет 241 байтом .
Кевин Круйссен,
@KevinCruijssen Определенно могу удалить место, чтобы сделать это Contains(c)Then, я просто пропустил это. Мне нравится то, что вы думаете, но я использую gв качестве дозорного, чтобы увидеть, содержит ли строка номер или нет. Ваша ссылка дает неправильные ответы, но я посмотрю, смогу ли я переработать некоторую внутреннюю логику в соответствии с тем, что вы думаете.
Брайан Дж
Ах, упс .. Это действительно не удается .. Теперь это только вывод ввода. Виноват. Не следует делать такие комментарии, когда вечер и я устал от работы. ;)
Кевин Круйссен
1

Желе , 20 байт

Пиф побеждает желе. Иди мистер Xcoder!

Df⁹LD¤ȯeṆ
0ç1#ɓ;
1Ç¡

Полная программа, принимающая ввод из STDIN и выводящая в опции формата списка, используя представление списка Jelly *. Использует стандартное индексирование на основе 0.

* Не списки одного элемента имеют не окружающие [], поэтому 0выходы 1, а 1выходы и [1, 0]т.д.

Попробуйте онлайн!

Как?

Df⁹LD¤ȯeṆ - Link 1, can append n to current? n, number; current, list
D         - convert n to decimal list
     ¤    - nilad followed by link(s) as a nilad:
  ⁹       -   chain's right argument, current
   L      -   length
    D     -   convert to a decimal list
 f        - filter discard from left if not in right
       e  - n exists in current?
      ȯ   - left logical OR right (empty lists are falsey)
        Ṇ - logical NOT

0ç1#ɓ; - Link 2, append next number: current, List
   #   - n find (count up finding first n matches):
  1    - ...finding: 1 match
0      - ...stating at: n=0
 ç     - ...doing: the last link as a dyad (left=n, right=current)
    ɓ  - new swapped-arg-dyadic chain (left = current, right = list of the found n)
     ; - concatenate

1Ç¡ - Main link: no arguments
1   - initialise the return value to 1
  ¡ - repeat input() times:
 Ç  -   last link (2) as a monad
    - implicit print
Джонатан Аллан
источник