I have two lists that have the same number of elements. In the first list, an element represents a category type. In the second list, an element represents a kind of cost. Indices corresponds to each other.
For example:
category_list = [1, 2, 2, 1, 3, 3, 3, 3, 4, 2]
cost_list = [30, 45, 21, 22, 21, 32, 11, 12, 13, 11]
On the condition that I pick one for every category, I would like to minimize the cost. How can I implement this? Faster, better. Thank you for your help.
CodePudding user response:
I recommended this code. In here we use the prebuilt method 'zip' in python to iteratively get the category_list and cost_list so I supposed it is good practice and then I using conditional expression to create my logic. First I want to determine in that category already in my x_dict in that expression is true I using 'min' prebuilt method to compare the value that already exists and the new value of the related key. So it is helpful to manage our logic. Otherwise, that key does not already exist then we can added key-value pair for the first time. the dictionary key is must be unique that's why we using this logic.
category_list = [1, 2, 2, 1, 3, 3, 3, 3, 4, 2]
cost_list = [30, 45, 21, 22, 21, 32, 11, 12, 13, 11]
x_dict=dict()
for cat,cost in zip(category_list,cost_list):
if cat in x_dict:
x_dict[cat]=min(x_dict[cat],cost)
else:
x_dict[cat]=cost
print(x_dict)
Output
{1: 22, 2: 11, 3: 11, 4: 13}
We can use the zip method directly and convert it to the dictionary. It can filter the unique keys but the case is it given the last value for the related key which we use like given below.
x=dict(zip(category_list,cost_list))
print(x)
output
{1: 22, 2: 11, 3: 12, 4: 13}
You can see last cost of the given list assign to the related category. Thats we give that logic for our code.
CodePudding user response:
You can store the minimum cost of each category in a dict
.
category_list = [1, 2, 2, 1, 3, 3, 3, 3, 4, 2]
cost_list = [30, 45, 21, 22, 21, 32, 11, 12, 13, 11]
min_cst = dict()
for cat, cst in zip(category_list, cost_list):
if cat in min_cst:
min_cst[cat] = min(min_cst[cat], cst)
else:
min_cst[cat] = cst
print(min_cst)
# {1: 22, 2: 11, 3: 11, 4: 13}
The time complexity is O(N)
and space complexity is O(N)
.
CodePudding user response:
Since there are already three nearly-identical answers using dict
, here is a different answer using min
only once per category:
category_list = [1, 2, 2, 1, 3, 3, 3, 3, 4, 2]
cost_list = [30, 45, 21, 22, 21, 32, 11, 12, 13, 11]
pick_indices = [min((i for i in range(len(cost_list)) if category_list[i] == cat), key=lambda i: cost_list[i]) for cat in set(category_list)]
pick_totalcost = sum(cost_list[i] for i in pick_indices)
Or alternatively:
pick_costs = [min(cost for i,(cost,cat) in enumerate(zip(cost_list, category_list)) if cat == c) for c in set(category_list)]
pick_totalcost = sum(pick_costs)
CodePudding user response:
Solution 1:
You can iterate over category_list
and save a min of cost_list
in a dictionary that key is category_list
and you can use dictionary.get()
and replace min with the minimum that exist before in the dictionary.
category_list = [1, 2, 2, 1, 3, 3, 3, 3, 4, 2]
cost_list = [30, 45, 21, 22, 21, 32, 11, 12, 13, 11]
dct_min = {}
for idx in range(len(category_list)):
min_item = dct_min.get(category_list[idx], cost_list[idx])
# alternative solution by thanks @Stef
# min_item = dct_min.setdefault(category_list[idx], cost_list[idx]); if cost_list[idx] < min_item: ...
if cost_list[idx] <= min_item:
dct_min[category_list[idx]] = cost_list[idx]
print(dct_min)
Output:
{1: 22, 2: 11, 3: 11, 4: 13}
Solution 2: (you can use zip
then sort tuple
first base index0
then index1
and convert sorted tuple
to dictionary
and we know in dictionary
we have only one key
.)
zip_lsts = list(zip(category_list, cost_list))
dict(sorted(zip_lsts, key=lambda element: (element[0], element[1]),reverse=True))
# {4: 13, 3: 11, 2: 11, 1: 22}