Как сортировать указанные c элементы в указанном c порядке в списке

Question

Привет всем, я пытаюсь сделать алгоритм, который сортирует определенные c элементы в определенном порядке. Предположим, что у нас есть список предметов: [1, 2, 1, 3, 3, 3, 2, 2, 2, 2, 2, 1, 3, 2, 2, 1] существует три разных типа предметов здесь: 1, 2 и 3. Я хочу отсортировать этот список, чтобы иметь последовательность элементов, которые соответствуют тем же типам. В процессе сортировки мы не можем перемещать элементы позиции, мы просто можем удалить некоторые элементы, и результат должен быть самым длинным. Результат этого алгоритма должен быть:
[1, 1, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2] Я не знаю, почему мой алгоритм не работает:

# start list
givenList = [1, 2, 1, 3, 3, 3, 2, 2, 2, 2, 2, 1, 3, 2, 2,1]
# whish list (just for an example)
whish = [1, 1, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2]
# list grouped by items ( [ [1], [2], [1], [3, 3, 3], [2, 2, 2, 2, 2] ....])
sortedList = []

# we group the elements
lastElement=0
for currentElement in givenList :
  if currentElement != lastElement :
    sortedList.append([currentElement])
    lastElement=currentElement
  else : sortedList[-1].append(currentElement)

# we print the grouped items
for index, element in enumerate(sortedList) :
  print("Bloc : ", index , " contient : " , element)

# we sort the same elements by group
result=[]
for index, element in enumerate(sortedList) :
  # we pass if it's the first group because he has no backward element
  if(index == 0) : continue
  # we pass if it's the last group because he has no afterward element
  if(index == len(sortedList) - 1) : continue
  # backward group
  backwardList = sortedList[index - 1]
  # current group
  currentList = sortedList[index]
  # afterward group
  forwardList = sortedList[index + 1]
  # if the backward groupelement type is the same as the forward
  if backwardList[0] == forwardList[0] :
    # and if the backwardlist contains more element that the current group
    if(len(backwardList) >= len(currentList)) :
      # we add the concatenation of the backwards and the forwards group
      result.append(backwardList + forwardList)
  elif backwardList[0] != forwardList[0] :
    # else we just add the current group
    result.append(currentList)

# we degroup the grouped and sorted list
resultSorted=[]
for e in result:
  for i in e:
    resultSorted.append(i)

# 
print("#"*20)
print("Given : ", givenList)
print("Whish : ", whish)
print("Result : ", resultSorted)
print("#"*20)

Answer 1

Вы можете попробовать эту реализацию с itertools.groupby:

from itertools import groupby

l = [1, 2, 1, 3, 3, 3, 2, 2, 2, 2, 2, 1, 3, 2, 2, 1]

def get_max(elems, current_elems=None):
    if current_elems is None:
        current_elems = []

    for idx, (color, count) in enumerate(elems):
        if color in [c for c, _ in current_elems[:-1]]:
            continue
        yield current_elems + [(color, count)]
        yield from get_max( elems[idx+1:], current_elems + [(color, count)] )

elems = [(v, sum(1 for _ in g)) for v, g in groupby(l)]
l, _ = max(((v, sum(c for _, c in v)) for v in get_max(elems)), key=lambda k: k[1], default=[[], None])

out = []
for v, g in groupby(l, key=lambda k: k[0]):
    for _, c in g:
        out.extend([v] * c)

print(out)

Отпечатки:

[1, 1, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2]

---

Другие тестовые случаи:

l = [1, 2, 3]       # [1, 2, 3]
l = [1, 2, 3, 1, 1] # [2, 3, 1, 1]