python-3.x - 从多个列表中只选择一个唯一元素

94 1

我想要从多个列表中选择一个元素,并且它们不重复。

例如,在代码的末尾,我得到一个输出:


{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]}



有没有另一种方法来解决这个问题。

时间: 原作者:

134 1

我使用python函数的sorted()进行排序,

{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) 



原作者:
69 2

使用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可以变慢或变快,具体取决于列表的“稀疏性”,

在这个例子中 4! == 4 * 3 * 2 * 1 == 24置换解决方案,以及 3 * 4 * 2 * 4 == 96 笛卡尔积的解决方案。

原作者:
...