Sắp xếp 2 danh sách bằng Python dựa trên tỷ lệ của từng phần tử tương ứng hoặc dựa trên danh sách thứ ba

Question

Tôi đang cố gắng viết các triển khai khác nhau cho một phân số knapsack problem.

Đối với điều này tôi có 2 mảng:

1. Values ​​
2. Trọng lượng

Các yếu tố giá trị [n] tương ứng với trọng lượng nguyên tố [n]. Vì vậy, chúng ta có thể tính toán value_per_unit như:

for I in range(values): 
    value_per_unit.append(values[I]/weights[I]) 
value_per_unit.sort() 

bây giờ tôi cần 2 mảng (giá trị và khối lượng) để được sắp xếp theo các mảng value_per_unit

ví dụ: Nếu

• giá trị = [60, 100, 120]
• trọng số = [20, 50, 30]

.210

Sau đó

• values_per_unit = [3.0, 2.0, 4.0]

• và do đó values_per_unit_sorted sẽ [2.0, 3.0, 4.0]

tôi cần các giá trị và trọng lượng mảng để trở thành:

• giá trị_sorted = [100,60,120]
• weights_sorted = [50,20,30]

Có cách nào để đạt được điều này sử dụng các hàm lambda đơn giản?

tôi vẫn có thể làm một cái gì đó như thế này, nhưng có vẻ như không hiệu quả mỗi lần tôi cần phải truy cập vào các yếu tố:

weights[(value_per_unit_sorted.index(max(value_per_unit_sorted)))] 

Answer 1

Trong một dòng:

values, weights = zip(*sorted(zip(values, weights), key=lambda t: t[0]/t[1])) 

---

Để giải thích : Trước tiên, hãy nén các danh sách để ghép nối chúng.

pairs = zip(values, weights) 
# [(60, 20), (100, 50), (120, 30)] 

Sau đó, sắp xếp theo thương số của giá trị theo trọng lượng.

sorted_pairs = sorted(pairs, key=lambda t: t[0]/t[1]) 
# [(100, 50), (60, 20), (120, 30)] 

Cuối cùng, giải nén chúng trở lại vào danh sách riêng biệt.

values, weights = zip(*sorted_pairs) 
# (100, 60, 120), (50, 20, 30) 

---

Một cách khác là để xây dựng bộ dữ liệu chứa một cách rõ ràng tỷ lệ là yếu tố đầu tiên.

ratios, values, weights = zip(*sorted((v/w, v, w) for v, w in zip(values, weights))) 

Trước đây có vẻ hơi nhanh hơn trong một số thử nghiệm nhanh. Nếu bạn đang tìm kiếm một thuật toán tối ưu, có thể bạn sẽ phải bỏ mọi thứ và giải pháp sẽ không ngắn gọn.

Và để giải quyết các bình luận từ @TomWyllie, nếu bạn đã có danh sách các tỷ lệ, bạn có thể sử dụng:

ratios, values, weights = zip(*sorted(zip(ratios, values, weights))) 

Lưu ý rằng hai giải pháp cuối cùng này khác với các giải pháp ban đầu trong trường hợp hai cặp có tỷ lệ bằng nhau. Các giải pháp này sẽ sắp xếp thứ hai theo giá trị, trong khi giải pháp đầu tiên sẽ giữ cho các mục theo thứ tự giống như danh sách gốc.

Answer 2

Đối với một giải pháp rõ ràng hơn (nhưng cho là ít pythonic), tạo ra một danh sách các chỉ số, được sắp xếp theo giá trị tại chỉ số đó trongvalue_per_unit, và sắp xếp lại values và weights cho phù hợp.

sorted_indices = [index for index, value in 
        sorted(enumerate(value_per_unit), key=lambda x: x[1])] 
values = [values[i] for i in sorted_indices] 
weights = [weights[i] for i in sorted_indices] 

print(values, weights) 

Đầu ra:

([100, 60, 120], [50, 20, 30]) 

Bạn có thể sắp xếp gọn gàng này lên, loại bỏ các vòng thêm không cần thiết sử dụng zip, và với một biểu thức máy phát điện;

values, weights = zip(*((values[i], weights[i]) for i, value in 
        sorted(enumerate(value_per_unit), key=lambda x: x[1]))) 
print(values) 
print(weights) 

Đầu ra nào;

(100, 60, 120) 
(50, 20, 30) 

Lưu ý các giá trị cuối cùng là tuples không lists. Nếu bạn thực sự cần đầu ra là một danh sách, một đơn giản values, weights = map(list, (values, weights)) là đủ. Bạn thậm chí có thể quấn nó vào một lớp lót, mặc dù vào thời điểm đó nó có thể nhận được khá khó khăn để làm theo những gì đang xảy ra.

Answer 3

Một cách thanh lịch để làm điều này là để tạo ra một danh sách đa chiều với các giá trị và trọng lượng:

for i in range(len(values)): 
    values_and_weights.append([values[i], weights[i]) 
# The resulting list is [[60, 20], [100, 50], [120, 30]] 

Sau đó, sử dụng phương pháp loại với giá trị chia theo trọng lượng là chìa khóa.

values_and_weights.sort(key=(lambda x: x[0]/x[1])) 

Answer 4

Vấn đề bạn đang gặp là nguyên nhân bằng cách sử dụng một trường tính toán trên mỗi phần tử (yếu tố tôi sẽ có giá trị tính values[I]/weights[I]). Để giải quyết điều này và vẫn giữ cho nó rất dễ hiểu, bạn có thể biến nó thành một tuple của mẫu đơn này: (calculated_value, (value, weight)), cho mỗi phần tử.

Cách tiếp cận này giúp dễ đọc và dễ hiểu.Nhìn vào các giải pháp sau đây:

values = [60, 100, 120] 
weights = [20, 50, 30] 
value_per_unit = [] 

for I in range(len(values)): 
    value_per_unit.append((values[I]/weights[I], (values[I], weights[I]))) 
sorted_value_per_unit = sorted(value_per_unit, key=lambda x: x[0]) 

sorted_values = [] 
sorted_weights = [] 
for I in range(len(values)): 
    (value, weight) = sorted_value_per_unit[I][1] 
    sorted_values.append(value) 
    sorted_weights.append(weight) 

print(str(sorted_values)) 
print(str(sorted_weights)) 

Ngoài ra, lưu ý rằng tôi sửa đổi vòng lặp từ mã ban đầu của bạn:

range(values) đã thay đổi range(len(values))

Kể từ phạm vi sẽ cần chiều dài của danh sách, chứ không phải hơn chính danh sách đó.