Проблема состоит из трех основных сложностей, помимо простого распределения элементов по спискам:
- списки исключений предотвращают простое разбиение;
- сами списки исключений могут иметь двойные исключения среди них.поэтому простое решение на основе множеств не сработает;
- списки исключений позволят найти решение, но любой подход к заполнению может привести к преждевременному заполнению списка результатов элементами, которые могли попасть в другие списки..
В результате, работающее решение состоит в том, что оно просто пытается добавить элементы в первый доступный им список, но если у него возникают проблемы, оно просто возвращается к предыдущему добавлению -и если это в конечном итоге приводит к проблемам, к предыдущему добавлению и т. д.
В функциональных языках этот тип возврата может быть очень хорошо реализован в рекурсивной функции, но, поскольку максимальная глубина рекурсии Python очень ограниченаитеративный подход, вероятно, лучше - особенно с учетомразмер набора данных.
Вот мое решение:
# generate list of identifiers
biglist = list(range(20))
# arbitrary exclusions, with some duplication
a_exc = [0, 2, 8, 15]
b_exc = [1, 3, 4, 6, 12]
c_exc = [0, 1, 5, 6, 7, 9, 1, 0]
def distribute(xs, n, exclusions):
# will distribute the contents of list xs over n lists, excluding items from exclusions[m] for the m-th list
# returns a list of lists (destructive, so xs will be empty after execution, pass in a copy to avoid)
# initialise result lists
result = [set() for _ in range(n)]
# calculate maximum size for each of the list for a balanced distribution
result_size = len(xs) // n
if len(xs) % n > 0:
result_size += 1
# initialise a list of additions, to allow for backtracking; recursion would be cleaner,
# but your dataset is too large an Python is not a functional language that is optimised for this
additions = []
# add all xs to the lists, trying the list in order, backtracking if lists fill up
while xs:
# get the last element from the list
x = xs.pop()
# find a place to add it, starting at the first list
i = 0
while True:
while i < n:
# find a list that's not full and can take x
if len(result[i]) < result_size and x not in exclusions[i]:
# add it
result[i].add(x)
# remember this exact addition
additions.append((i, x))
break
i += 1
# if x could not be added (due to exclusions and full lists)
if i == n:
# put current x back at the end of the list
xs.append(x)
# go back to the previous x
i, x = additions.pop(-1)
# take it out from the list it was put into
result[i].remove(x)
# try putting it in the next list available
i += 1
else:
break
return result
spread_lists = distribute(biglist, 3, [a_exc, b_exc, c_exc])
print(spread_lists)
Есть место для оптимизации, но я думаю, что это работает.
Фактически, после генерации несколькихДля больших наборов тестов я обнаружил, что алгоритм нуждается в оптимизации , и это на самом деле довольно просто: отсортируйте входной список по количеству исключений, которые ему соответствуют.Таким образом, идентификаторы, которые исключены n раз, обрабатываются раньше тех, которые исключены n-1 раз и т. Д.
Это добавляет следующую строку в начало distribute:
# sort the input by most exclusions, most exclusions last, as list is processed in reverse order
xs = [x for _, x in sorted([([x in exc for exc in exclusions].count(True), x) for x in xs])]
Это дает дополнительное преимущество: больше не вычищать xs, если это было нежелательно.