Я разделил проблему на подзадачи ... Тест, чтобы проверить, все ли работает должным образом:
# These are the two lists I want to pair
a = [ "apples"
, "oranges"
, "bananas"
, "blueberries" ]
b = [ "apples"
, "blueberries"
, "oranges"
, "bananas" ]
# This is the expected result
expected = [ (0, 0)
, (None, 1)
, (1, 2)
, (2, 3)
, (3, None) ]
# Test the function gets the correct result
assert expected == get_indexes_for_best_pairing(a, b)
print("Tests pass!")
1. Создайте список всех пар.
Создайте карту значений из списка A со списком связанных индексов ...
def map_list(list):
map = {}
for i in range(0, len(list)):
# Each element could be contained multiple times in each
# list, therefore we need to create a sub array of indices
if not list[i] in map:
map[list[i]] = []
# Add the index onto this sub array
map[list[i]].append(i)
return map
map будет выглядеть ...
{ "apples": [0]
, "oranges": [1]
, "bananas": [2]
, "blueberries": [3] }
Найдите все пары по списку перекрестных ссылок B ...
def get_pairs(a, b):
map = map_list(a)
pairs = []
for i in range(0, len(b)):
v = b[i]
if v in map:
for j in range(0, len(map[v])):
pairs.append((map[v][j], i))
return pairs
pairs следующие ...
[ (0, 0)
, (3, 1)
, (1, 2)
, (2, 3) ]
2. Получите баллы для каждой пары.
Просто переберите пары и найдите значение в исходном списке:
def get_pairs_scores(pairs, a):
return [len(a[i]) for i, _ in pairs]
3. Создайте список пар, которые исключаются из каждой пары.
Для каждой пары найдите другие пары, которые она исключает ...
def get_pairs_excluded_by_pair(pairs, i):
# Check if the context pair excludes the pair, if both of the
# pairs indexes are greater or less than the other pair, then
# the pairs are inclusive and we will have a positive number,
# otherwise it will be negative
return [j for j in range(0, len(pairs))
# If the current context pair is also the pair we are comparing
# skip to the next pair
if i != j
and ((pairs[i][0] - pairs[j][0]) * (pairs[i][1] - pairs[j][1]) < 0)]
def get_pairs_excluded_by_pairs(pairs):
excludes = []
for i in range(0, len(pairs)):
excludes.append(get_pairs_excluded_by_pair(pairs, i))
return excludes
Метод pairs_excludes вернет ...
[ []
, [2, 3]
, [1]
, [1] ]
4. Рассчитайте общий совокупный балл для каждой пары за вычетом пар, которые она исключает.
Плюс оценка пар, которые исключаются парами, которые он исключает ... и т. д. и т. д.
Используйте алгоритм сначала в глубину, чтобы просмотреть ациклический график исключений, чтобы получить совокупный балл для каждой пары ... Это основа того, что нам нужно сделать ...
def get_cumulative_scores_for_pairs(pairs, excludes, scores):
cumulative = []
# For each pair referenced in the excludes structure we create a new
# graph which starting from that pair. This graph tells us the total
# cumulative score for that pair
for i in range(0, len(pairs)):
score = 0
# Keep a reference of the nodes that have already been checked by
# in this graph using a set. This makes the graph acyclic
checked = set()
checked.add(i)
# We keep a note of where we are in the graph using this trail
# The pairs relate to the index in the pair_excludes. if pair
# first is x and pair second is y it refers to pair_excludes[x][y]
trail = []
# We start the current x, y to be the first exclude of the current
# start node
current = [i, 0]
# Sorry, tree traversal... Might not very readable could
# be done with recursion if that is your flavour
while True:
# Get the referenced excluded node
if len(excludes[current[0]]) > current[1]:
j = excludes[current[0]][current[1]]
# We do not want to calculate the same pair twice
if not j in checked:
# It has not been checked so we move our focus to
# this pair so we can examine its excludes
trail.append(current)
# We mark the pair as checked so that we do
# not try and focus on it if it turns up again
checked.add(j)
current = [j, 0]
# We perform a trick here, where when we traverse
# down or up a layer we flip the sign on the score.
# We do this because the score for pairs that we
# exclude need to be subtracted from the score whereas
# scores for pairs that we now can include because of
# that exclude need to be added to the score.
score = -score
# It the pair has already been checked, check its
# next sibling next time around
else:
current[1] += 1
# There are no more nodes to check at this level
else:
# We subtract the cumulative score from the score of the
# pair we are leaving. We do this when we traverse back up
# to the parent or as the last step of each graph finally
# subtracting the total cumulative score from the start node
# score.
score = scores[current[0]] - score
if len(trail):
# Pop the next item on the trail to become our context
# for the next iteration
current = trail.pop()
# Exit criteria... The trail went cold
else:
break
# Add the score to the array
cumulative.append(score)
return cumulative
Этот метод должен возвращать массив, который выглядит как ...
[ 6
, -3
, 3
, 3 ]
5. Выбирайте только лучшие пары.
Затем нам нужно сохранить индекс с оценкой, чтобы мы могли выполнить сортировку по счету, не теряя индекс. Отсортируйте совокупные баллы, чтобы создать список показателей _14 _...
# Sort pairs by score retaining the index to the pair
arr = sorted([(i, cumulative[i])
for i in range(0, len(cumulative))],
key=lambda item: item[1])
Это выглядит как...
[ (1, -3)
, (2, 3)
, (3, 3)
, (0, 6) ]
Выбирайте элементы с наибольшим количеством очков, удаляя исключенные элементы по ходу работы, таким образом мы сохраняем лучшие пары и отбрасываем худшие ...
def get_best_pairs(a, b):
pairs = get_pairs(a, b)
excludes = get_pairs_excluded_by_pairs(pairs)
scores = get_pairs_scores(pairs, a)
cumulative = get_cumulative_scores_for_pairs(pairs, excludes, scores)
# Sort pairs by score retaining the index to the pair
arr = sorted([(i, cumulative[i])
for i in range(0, len(cumulative))],
key=lambda item: item[1])
# Work through in order of scores to find the best pair combination
top = []
while len(arr):
topitem = arr.pop()
top.append(topitem[0])
# Remove the indices that are excluded by this one
arr = [(i, score)
for i, score in arr
if i not in excludes[topitem[0]]]
# Sort the resulting pairs by index
return sorted([pairs[i] for i in top], key=lambda item: item[0])
Наш список top будет выглядеть так, как если бы пара с индексом 1 была отброшена, потому что она имела низкий балл и была исключена парами с более высоким баллом ...
[ (0, 0)
, (1, 2)
, (2, 3) ]
6. Постройте результат
Отсортируйте выбранные пары и создайте результат, увеличивая каждый индекс до следующей пары. Когда у нас заканчиваются пары, увеличиваем, пока не дойдем до конца каждого списка ...
def get_indexes_for_best_pairing(a, b):
pairs = get_best_pairs(a, b)
result = [];
i = 0
j = 0
next = None
pair = None
while True:
# This is the first loop or we just dropped a pair into the result
# vector so we need to get the next one
if next == None:
# Get the next pair and we will increment the index up to this
if len(pairs):
next = pairs.pop(0)
pair = next
# No more pairs increment the index to the end of both lists
else:
next = (len(a), len(b))
pair = None
# We increment the index of the first list first
if i < next[0]:
result.append((i, None))
i += 1
# We increment the index of the second list when first has reached
# the next pair
elif j < next[1]:
result.append((None, j))
j += 1
# If both indexes are fully incremented up to the next pair and we
# have a pair to add we add it to the result and increment both
# clearing the next parameter so we get a new one next time around
elif pair != None:
result.append((pair[0], pair[1]));
i += 1
j += 1
next = None
# We reached the end
else:
break
return result
И, наконец, наш результат будет выглядеть так ...
[ (0, 0)
, (None, 1)
, (1, 2)
, (2, 3)
, (3, None) ]
person
Community
schedule
02.09.2012
