Можно ли из заданных цифр составить последовательность чисел, являющуюся арифметической прогрессией?

Question

[Артем Зинкин]

Задана строка, состоящая из цифр. Длина строки не превышает 15 символов.

Требуется написать программу, которая определит, можно ли из заданных цифр составить последовательность чисел, являющуюся арифметической прогрессией. В новой последовательности должны использоваться все цифры исходной строки, каждая по одному разу.

Входные данные: последовательность цифр.
51791

Выходные данные: искомая последовательность чисел (не менее трёх), записанных через пробел, либо 0, если последовательность составить не удалось.
5 7 9 11

Comments

[Сергей Соколов]

Это задание, а не вопрос.

Покажите, что вы сделали, как подошли к задаче, на каком моменте застряли.
Как её решить самым некрасивым и сложным неэффективным способом?

[Артем Зинкин]

Сергей Соколов, вы правы.
Ничего интереснее решения в лоб, я не придумал.
Из исходной последовательности строиться возможные комбинации, меняется порядок чисел.
Каждая из получившихся последовательностей разбивается на группы чисел в количестве от 3 штук.
Каждый такой набор проверяется на арифметическую прогрессию.
Это срабатывает до 6 символов.

[Taus]

Последовательность с шагом 0 считается последовательностью?

[longclaps]

Taus, да, как и с отрицательным, по определению а.п. Впрочем, отрицательный шаг нетрудно превратить в положительный.

[Артем Зинкин]

Taus, Да

[Артем Зинкин]

longclaps, последовательность строиться из цифр, поэтому будет только возрастающей, либо статичной.

[longclaps]

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

да, как и с отрицательным, по определению арифметической прогрессии

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

Артем Зинкин, что это было?
Да, подкиньте больше входных данных, посмотрю, на чем я обломаюсь (вы ведь на 6 цифрах, да?)

[Артем Зинкин]

longclaps, а в чем проблема набрать входные данные? Берите любую арифметическую (или нет) последовательность и разбиваете на цифры, вот вам входные данные.
1 500 999 – последовательность, шаг 499
1500999 – входные данные

Answer 1

[Сергей Соколов]

Можно всегда

В любом случае, при любых цифрах, числом более одной, можно составить «последовательность» всего из двух чисел и объявить её арифметической % )

51791
5,  5 + 1786 = 1791, третьим было бы 3577

Если серьёзно, разбейте на подзадачи.

Вот, дан набор чисел. Как быстро понять, является ли он арифм. последовательностью?
Наверное, это должен быть набор из 3 и более чисел. Отсортировать по возрастанию, получить разницу между 0-м и 1-м. Двигаться далее, сравнить 2й и 1й. Как только разница отличится от первой, это fail. Если успешно дошли до конца массива и везде разница одна и та же — это успех, это арфим. последовательноть.

Другая подзадача: из набора цифр составить все возможные числа. Чисел должно получиться 3 и более. Во всех вариантах перестановок, но с учетом повторяющихся цифр в исходном наборе.

Можно добавить всяких оптимизаций. Например, проверять чётность.
В арифметической последовательности чётность либо постоянная, либо чередуется через раз. Чётное число оканчивается на чётную цифру. Поэтому если в исходном наборе есть всего одна нечетная цифра, либо её место не в конце числа, либо в последовательности всего три числа и эта цифра в конце среднего.

Comments

[Артем Зинкин]

Сергей Соколов, это было бы неинтересно. Текст задания:
искомая последовательность чисел (не менее трёх)

[Сергей Соколов]

Артем Зинкин, обновил ответ

[Артем Зинкин]

Сергей Соколов, с первым пунктом согласен. Проверяем можем ли получить последовательность из цифр, не составляя из них числа.

Второй пункт такой же, как я описал в комментарии к вопросы.

[Сергей Соколов]

Артем Зинкин, первый пункт, я имею в виду, функцию, принимающую любой массив чисел.
Вот пришёл на вход массив [9, 11, 7, 5] и надо вернуть true / false – составляется ли из данных чисел арифм. прогрессия.

Второй – отдельная задача комбинаторики. Дан набор символов (некоторые могут повторяться). Надо составить из них все возможные «слова», так, чтобы слова не повторялись и их было 3 или более.

[Артем Зинкин]

Сергей Соколов, на вход приходит набор цифр, а не чисел. Но в целом, да. Первый пункт — функция, которая определяет из полученных чисел, можно ли составить прогрессию.

Вопрос тогда по второму пункту. Эффективное разбиение на числа.

[Сергей Соколов]

Артем Зинкин, в финальном решении, сначала, разумеется, идёт «Второй» пункт, а затем проверяется «Первым» ) Написал в таком порядке, т.к. «Первый» проще в реализации.

Про «Второй» см. ответ.

[Артем Зинкин]

Сергей Соколов, ага и реализацию из примера нужно повторить для всех перестановок в строке длинной 15 символов, которых 1307674368000 штук. Для каждой 32592. Из которых, в худшем случае, нам не подойдет ни одна.

[Сергей Соколов]

Артем Зинкин, тут немного другая комбинаторика: необходимо задействовать строго все имеющиеся цифры.
Это называется «перестановки» и формула немного другая.

[longclaps]

для всех перестановок в строке длинной 15 символов, которых 1307674368000 штук

Артем Зинкин, цифр всего-то 10, так что перестановок будет поменьше.

[Артем Зинкин]

longclaps, перестановки зависят от количества чисел, а не от самих цифр:
12 – две цифры, две перестановки.
112 – две цифры, три перестановки.

[longclaps]

Артем Зинкин, а это что?

для всех перестановок в строке длинной 15 символов, которых 1307674368000

вот тут вы делаете слишком сильное утверждение для 15-символьных строк произвольного состава.

[Артем Зинкин]

longclaps, это утверждение основано на математике:
15 * 14 * 13 * 12 ... * 4 * 3 * 2 = 1307674368000

[longclaps]

12 – две цифры, две перестановки.
112 – две цифры, три перестановки.

Артем Зинкин, а это утверждение основано на чем? )))

[Артем Зинкин]

longclaps, вы решили всё подвергнуть сомнению?

1221 – цифры (1,2) две, перестановок тоже две.
112121211 – цифры (1,2) две, перестановок три.

[Сергей Соколов]

Артем Зинкин, в данном случае всё так. Напомню формулы.
n уникальных можно перставить n! способами (1 * 2 * 3 * .. * n)
Если есть повторяющиеся элементы, например, "1" повторяется дважды, а "5" трижды, то надо разделить на произведение факториалов: n! / (2! * 3!)
В примере 12 ответ 2! = 1 * 2 = 2
В примере 112 ответ 3! / 2! = 1 * 2 * 3 / 1 * 2 = 3
В вопросе 51791 число перестановок 5! / 2! = 60

Answer 2

[longclaps]

'012' 0 1 2
'0123' 0 1 2 3
'01234' 0 1 2 3 4
'012345' 0 1 2 3 4 5
'0123456' 0 1 2 3 4 5 6
'01234567' 0 1 2 3 4 5 6 7
'012345678' 0 1 2 3 4 5 6 7 8
'0123456789' 0 1 2 3 4 5 6 7 8 9
'01234567890' 0 18 36 54 72 90
'012345678901' 0 1 2 3 4 5 6 7 8 9 10
'0123456789012' 56 94 132 170 208
'01234567890123' 57 120 183 246 309
'012345678901234' 100 312 524 736 948
'0123456789012345' 0 181 362 543 724 905
'01234567890123456' 58 179 300 421 542 663
'012345678901234567' 50 1736 3422 5108 6794
'0123456789012345678' 6 139 272 405 538 671 804
'01234567890123456789' 0 9 18 27 36 45 54 63 72 81 90
'012345678901234567890' 162 300 438 576 714 852 990
'0123456789012345678901' 28 37 46 55 64 73 82 91 100 109
'01234567890123456789012' 584 1007 1430 1853 2276 2699
'012345678901234567890123' 102 219 336 453 570 687 804 921
'0123456789012345678901234' 91 674 1257 1840 2423 3006 3589
'01234567890123456789012345' 105 984 1863 2742 3621 4500 5379
'012345678901234567890123456' 162 1300 2438 3576 4714 5852 6990
'0123456789012345678901234567' 1621 3002 4383 5764 7145 8526 9907
'01234567890123456789012345678' 72 163 254 345 436 527 618 709 800 891
'012345678901234567890123456789' 108 197 286 375 464 553 642 731 820 909

Написать можно, но на плохих данных ей поплохеет.

Comments

[Артем Зинкин]

longclaps, поясните появление этой строки
'0123456789012' 56 94 132 170 208

[longclaps]

Артем Зинкин, я её вычислил. А что не так?

[Артем Зинкин]

longclaps, кодом? Покажите?

[longclaps]

Артем Зинкин, вот один из вариантов:

from itertools import chain, permutations
import re


def main(s):
    t = tuple(filter(str.isdigit, s))
    le, alldigitscnt = len(t), [0] * 10
    for d in t:
        alldigitscnt[ord(d) - 48] += 1
    n = min(filter(None, alldigitscnt))
    if n > 2 and not any(c % n for c in alldigitscnt):
        return print(repr(s), *[''.join(chr(57 - i) * (c // n) for i, c in enumerate(alldigitscnt[::-1]))] * n)
    zero_head_str = re.compile(r'0\d+').match
    for parts in range(le, 2, -1):
        maxW, gaps = le // parts + bool(le % parts), parts - 1
        for maxS in map(''.join, permutations(t, maxW)):
            if zero_head_str(maxS):
                continue
            maxN = int(maxS)
            taildigitscnt = alldigitscnt[:]
            for d in maxS:
                taildigitscnt[ord(d) - 48] -= 1
            taildigits = ''.join(chain.from_iterable(chr(i) * w for i, w in enumerate(taildigitscnt, 48)))
            for minw in range(1, min(le // parts, (le - maxW) // gaps) + 1):
                for minS in map(''.join, permutations(taildigits, minw)):
                    if zero_head_str(minS):
                        continue
                    minN = int(minS)
                    if maxN <= minN:
                        continue
                    diff = maxN - minN
                    middigitscnt = taildigitscnt[:]
                    for d in minS:
                        middigitscnt[ord(d) - 48] -= 1
                    if diff % gaps:
                        continue

                    def chk(step):
                        tmp = middigitscnt[:]
                        for x in range(minN + step, maxN, step):
                            for d in str(x):
                                x = ord(d) - 48
                                if not tmp[x]:
                                    return False
                                tmp[x] -= 1
                        return not any(tmp)

                    if chk(diff // gaps):
                        return print(repr(s), *[minN + diff // gaps * i for i in range(gaps + 1)])
    print(f'{s!r} ups:(((')


S = '0123456789' * 2
for J in range(3, len(S) + 1):
    main(S[:J])

Answer 3

[xmoonlight]

Дано:
Строка цифр: 51791

Ограничения:
Минимальное количество элементов на выходе: 3

Эвристика:
Максимальное значение элемента: 975
Максимальное кол-во цифр в одном выходном элементе: 3
PS: Можно также, дополнительно, применить эвристику расчёта количества возможных разрядов в комбинациях, но это уже чуть сложнее.

1: 517, 9, 1 => 517-9=9-1 ? => false
2: 517, 1, 9 => 517-1=1-9 ? => false
3: 171, 5, 9 => ... => false
... и т.д.,
делаем сначала склейки, начиная с максимально возможных значений, затем сдвиг/перестановку одной цифры (и снова склейки), не превышая максимального числа цифр (в данном случае: 3) в одном тестируемом значении.
На каждом шаге проверяем равное расстояние.
Как только подобрали одно - оставляем эти цифры и проверяем оставшиеся ("погружение").