Выберите только один уникальный элемент из нескольких списков в Python

Question

Это не домашняя работа, которую я изо всех сил пытаюсь сделать, но я пытаюсь решить проблему (вот ссылка, если вы заинтересованы https://open.kattis.com/problems/azulejos).

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

Например, в конце моего кода я получаю вывод:

{1: [1, 2, 3], 2: [1, 2, 3, 4], 3: [2, 4], 4: [1, 2, 3, 4]}

Я хотел бы преобразовать это, например, в

{3: 4, 2: 2, 4:1, 1: 3} -- which is the sample answer that is in the website.

Но, насколько я понимаю, это также может быть просто

{1: 3, 2: 2, 3: 4, 4: 1}

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

import sys

n_tiles_row = int(sys.stdin.readline().rstrip())
# print(n_tiles_row) ==> 4

# BACK ROW - JOAO
back_row_price = sys.stdin.readline().rstrip()
# print(back_row_price) ==> 3 2 1 2

back_row_height = sys.stdin.readline().rstrip()
# print(back_row_height) ==> 2 3 4 3

# FRONT ROW - MARIA
front_row_price = sys.stdin.readline().rstrip()
# print(front_row_price) ==> 2 1 2 1

front_row_height = sys.stdin.readline().rstrip()
# print(front_row_height) ==> 2 2 1 3

br_num1_price, br_num2_price, br_num3_price, br_num4_price = map(int, back_row_price.split())
# br_num1_price = 3; br_num2_price = 2; br_num3_price = 1; br_num4_price = 2;

br_num1_height, br_num2_height, br_num3_height, br_num4_height = map(int, back_row_height.split())
# 2 3 4 3

fr_num1_price, fr_num2_price, fr_num3_price, fr_num4_price = map(int, front_row_price.split())
# 2 1 2 1

fr_num1_height, fr_num2_height, fr_num3_height, fr_num4_height = map(int, front_row_height.split())
# 2 2 1 3

back_row = {1: [br_num1_price, br_num1_height], 
2: [br_num2_price, br_num2_height], 
3: [br_num3_price, br_num3_height], 
4: [br_num4_price, br_num4_height]}
# {1: [3, 2], 2: [2, 3], 3: [1, 4], 4: [2, 3]}

front_row = {1: [fr_num1_price, fr_num1_height], 
2: [fr_num2_price, fr_num2_height], 
3: [fr_num3_price, fr_num3_height], 
4: [fr_num4_price, fr_num4_height]}
# {1: [2, 2], 2: [1, 2], 3: [2, 1], 4: [1, 3]}

_dict = {1: [], 
2: [], 
3: [], 
4: []
}

for i in range(n_tiles_row):
    _list = []
    for n in range(n_tiles_row):
        if(list(back_row.values())[i][0] >= list(front_row.values())[n][0] 
        and list(back_row.values())[i][1] >= list(front_row.values())[n][1]):
            _list.append(list(front_row.keys())[n])
            _dict[list(back_row.keys())[i]] = _list

print(_dict)
# {1: [1, 2, 3], 2: [1, 2, 3, 4], 3: [2, 4], 4: [1, 2, 3, 4]}

Пожалуйста, дайте мне знать, если есть другой подход к этой проблеме.

Answer 1

Вот решение, использующее тот же синтаксис, что и указанный вами код.

Хитрость здесь заключалась в том, чтобы упорядочить плитки сначала по возрастанию цены (вопрос, заданный для не убывающего), а затем по убыванию высоты так, чтобы самая высокая плитка следующей самой низкой цены в заднем ряду соответствовала самой высокойПлитка следующей самой низкой цены в первом ряду. Для этой сортировки я использовал функцию Python sorted(). См. Пример переполнения стека здесь .

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

В качестве примечания,Вы изначально утверждали, что словарь Python {3: 4, 2: 2, 4:1, 1: 3} эквивалентен {1: 3, 2: 2, 3: 4, 4: 1}. Хотя вы правы, вы должны помнить, что в словаре Python объекты по умолчанию не отсортированы, поэтому сравнивать ключи таким способом непросто.

import sys

n_tiles_row = int(sys.stdin.readline().rstrip())
# print(n_tiles_row) ==> 4

# BACK ROW - JOAO
back_row_price = sys.stdin.readline().rstrip()
# print(back_row_price) ==> 3 2 1 2

back_row_height = sys.stdin.readline().rstrip()
# print(back_row_height) ==> 2 3 4 3

# FRONT ROW - MARIA
front_row_price = sys.stdin.readline().rstrip()
# print(front_row_price) ==> 2 1 2 1

front_row_height = sys.stdin.readline().rstrip()
# print(front_row_height) ==> 2 2 1 3

# preprocess data into lists of ints
back_row_price = [int(x) for x in back_row_price.strip().split(' ')]
back_row_height = [int(x) for x in back_row_height.strip().split(' ')]
front_row_price = [int(x) for x in front_row_price.strip().split(' ')]
front_row_height = [int(x) for x in front_row_height.strip().split(' ')]

# store each tile into lists of tuples
front = list()
back = list()
for i in range(n_tiles_row):
    back.append((i, back_row_price[i], back_row_height[i]))  # tuples of (tile_num, price, height)
    front.append((i, front_row_price[i], front_row_height[i]))

# sort tiles by price first (as the price must be non-descending) then by height descending
back = sorted(back, key=lambda x: (x[1], -x[2]))
front = sorted(front, key=lambda x: (x[1], -x[2]))

# print(back) ==> [(2, 1, 4), (1, 2, 3), (3, 2, 3), (0, 3, 2)]
# print(front) ==> [(3, 1, 3), (1, 1, 2), (0, 2, 2), (2, 2, 1)]

possible_back_tile_order = list()
possible_front_tile_order = list()
for i in range(n_tiles_row):
    if back[i][2] > front[i][2]:  # if next lowest priced back tile is taller than next lowest priced front tile
        possible_back_tile_order.append(back[i][0])
        possible_front_tile_order.append(front[i][0])
    else:
        break

if len(possible_back_tile_order) < n_tiles_row:  # check that all tiles had matching pairs in back and front
    print("impossible")
else:
    print(possible_back_tile_order)
    print(possible_front_tile_order) 

Answer 2

A, возможно, неэффективный способ решения проблемы, состоит в том, чтобы сгенерировать все возможные «решения» (со значениями, которые могут отсутствовать в списках, соответствующих конкретному ключу) и выбрать «действительный» (для которого все значенияприсутствуют в соответствующих списках).

Один из способов сделать это с itertools.permutation (который способен вычислить все возможные решения, удовлетворяющие ограничению уникальности) будет:

import itertools


def gen_valid(source):
    keys = source.keys()
    possible_values = set(x for k, v in source.items() for x in v)
    for values in itertools.permutations(possible_values):
        result = {k: v for k, v in zip(keys, values)}
        # : check that `result` is valid
        if all(v in source[k] for k, v in result.items()):
            yield result


d = {1: [1, 2, 3], 2: [1, 2, 3, 4], 3: [2, 4], 4: [1, 2, 3, 4]}


next(gen_valid(d))
# {1: 1, 2: 2, 3: 4, 4: 3}

list(gen_valid(d))
# [{1: 1, 2: 2, 3: 4, 4: 3},
#  {1: 1, 2: 3, 3: 2, 4: 4},
#  {1: 1, 2: 3, 3: 4, 4: 2},
#  {1: 1, 2: 4, 3: 2, 4: 3},
#  {1: 2, 2: 1, 3: 4, 4: 3},
#  {1: 2, 2: 3, 3: 4, 4: 1},
#  {1: 3, 2: 1, 3: 2, 4: 4},
#  {1: 3, 2: 1, 3: 4, 4: 2},
#  {1: 3, 2: 2, 3: 4, 4: 1},
#  {1: 3, 2: 4, 3: 2, 4: 1}]

---

Это генерирует n! решений.

Подход "грубой силы", использующий декартово произведение над списками, дает prod(n_k) = n_1 * n_1 * ... * n_k решений (с n_k длиной каждого списка). В худшем случае (максимальная плотность) это решения n ** n, что асимптотически намного хуже факториала. В лучшем случае (минимальная плотность) это только 1 решение. Как правило, это может быть медленнее или быстрее, чем предложенное выше «решение по перестановке», в зависимости от «разреженности» списков.

Для среднего n_k прибл. n / 2, n! меньше / быстрее для n >= 6.

В среднем n_k прибл. n * (3 / 4), n! меньше / быстрее для n >= 4.

В этом примере имеются 4! == 4 * 3 * 2 * 1 == 24 решения для перестановок и 3 * 4 * 2 * 4 == 96 решения для декартовых произведений.