Расположите числа так, чтобы числа в блоке были уникальными

Question

Учитывая строку чисел, скажем «5556778», и число N (скажем, 2), переставьте строку так, чтобы числа в любом непрерывном блоке размера N были уникальными. например: для вышеуказанной строки и N = 2 одна перестановка может быть 5657578.

для N = 3: 5765785

найти расположение в линейном времени.

Answer 1

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

Теперь начните создавать списки размера N из 10 созданных вами групп, вытягивая их из верхней части каждого списка цифр. Если str.length() % N == 0, то этот алгоритм завершается успешно, когда используются все цифры. Вам нужно в особых случаях ситуации, когда это не так, но остальное должно быть тривиальным.

Answer 2

O (nk) жадное решение (n = размер ввода, k = основание ваших цифр), основанное на ответе Стефана Кендалла выше, но с пониманием того, что вы, вероятно, должны быть жадными и использовать целое число, которое вы используете чаще , Я не уверен, что это работает для всех входов, но я ломал голову, пытаясь придумать встречный пример, где жадность потерпит неудачу, и пока не нашел такого. Предупреждение: впереди грубый питон - я сделал это, чтобы быть быстрым и грязным, а не красивым.

Проверьте, можно ли использовать цифру, учитывая текущее состояние:

   def ok(s, n, v):
       l = len(s)
       if l < n:
           n = l
       if n < 1:
           return True
       if str(v) in s[-n:]:
           return False
       return True

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

   def go(counts, n):
       output = ""
       max = 0
       more = True

       while max >= 0:
         max = -1
         pos = -1
         more = False
         for i in range(10):
             if counts[i] > 0:
                 more = True
             if counts[i] > max and counts[i] > 0 and ok(output, n, i):
                 max = counts[i]
                 pos = i
         if max < 0:
             if more:
                 return "No solution"
             return output
         counts[pos] = counts[pos] - 1
         output = output + str(pos)

Основная функция:

   def blockify(s, fold):
       counts = [0,0,0,0,0,0,0,0,0,0]
       for letter in s:
         counts[int(letter)] = counts[int(letter)] +1
       return go(counts, fold)

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

Answer 3

Всегда ли [Длина строки] / N равно целому числу? Или может количество элементов в последнем «блоке»! = N?

Я бы составил список массивов, каждый из которых был инициализирован размером N.

Итерация по строке, добавление каждого номера к следующему доступному блоку, который еще не содержит этого номера. Продолжайте, пока не закончите.

Может быть циклом while или рекурсивной функцией, я оставлю детали реализации до вас.

EDIT: Хорошо, на основании новой информации, что блоки не являются отдельными, это похоже на модифицированный алгоритм сортировки.