Устройте номера так, чтобы числа в блоке были уникальными.

Question

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

При N = 3: 5765785

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

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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 

Helper, который делает всю работу - цикл по графам, найти один с максимальным числом повторений слева, который можно использовать, и выберите Это. Повторение.

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) 

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