Tìm tập hợp con với các phần tử xa nhau nhất với nhau

Question

Tôi có một câu hỏi phỏng vấn mà tôi dường như không thể tìm ra. Với một mảng có kích thước N, hãy tìm tập con của kích thước k sao cho các phần tử trong tập hợp con nằm xa nhau nhất. Nói cách khác, tối đa hóa khoảng cách tối thiểu giữa các phần tử.

Example: 

Array = [1,2,6,10] 
k = 3 

answer = [1,6,10] 

Cách bruteforce yêu cầu tìm tất cả tập hợp con có kích thước k là theo hàm mũ trong thời gian chạy.

Một ý tưởng tôi đã có là lấy giá trị đồng đều cách nhau từ mảng. Những gì tôi có ý nghĩa bởi đây là

1. Lấy 1 và yếu tố cuối cùng
2. tìm sự khác biệt giữa chúng (trong trường hợp này 10-1) và chia rằng bằng k ((10-1)/3 = 3)
3. di chuyển 2 con trỏ vào trong từ cả hai đầu, chọn ra các phần tử +/- 3 từ lựa chọn trước đó của bạn. Vì vậy, trong trường hợp này, bạn bắt đầu từ 1 đến 10 và tìm các phần tử gần nhất với 4 và 7. Sẽ là 6.

Điều này dựa trên những yếu tố cần được lan truyền đồng đều nhất có thể. Tôi không có ý tưởng làm thế nào để chứng minh nó hoạt động/không hoạt động. Nếu bất cứ ai biết làm thế nào hoặc có một thuật toán tốt hơn xin vui lòng chia sẻ. Cảm ơn!

Answer 1

Điều này có thể được giải quyết trong thời gian đa thức bằng DP.

Bước đầu tiên, như bạn đã đề cập, sắp xếp danh sách A. Cho X [i, j] là giải pháp để chọn phần tử j từ phần tử i thứ nhất A.

Hiện tại, X [i + 1, j + 1] = tối đa (min (X [k, j], A [i + 1] -A [k])) trên k < = i.

Tôi sẽ rời bước khởi tạo và ghi nhớ bước phụ tập để bạn có thể tiếp tục.

Trong ví dụ của bạn (1,2,6,10) nó hoạt động theo cách sau:

1 2 6 10 
1 - - - - 
2 - 1 5 9 
3 - - 1 4 
4 - - - 1 

Answer 2

Ý tưởng cơ bản là đúng, tôi nghĩ vậy. Bạn nên bắt đầu bằng cách sắp xếp mảng, sau đó lấy phần tử đầu tiên và cuối cùng, sau đó xác định phần còn lại.

Tôi không thể nghĩ ra thuật toán đa thức để giải quyết vấn đề này, vì vậy tôi sẽ đề xuất một trong hai tùy chọn.

Thứ nhất là sử dụng thuật toán tìm kiếm, kiểu nhánh và giới hạn vì bạn có một heuristic đẹp trong tay: giới hạn trên cho bất kỳ giải pháp nào là kích thước tối thiểu của khoảng cách giữa các phần tử được chọn cho đến thời điểm này đoán đầu tiên (các ô đều nhau, như bạn gợi ý) có thể cung cấp cho bạn một đường cơ sở tốt, điều này sẽ giúp cắt tỉa hầu hết các nhánh ngay lập tức. Điều này sẽ làm việc tốt cho các giá trị nhỏ hơn của k, mặc dù hiệu suất trường hợp xấu nhất là O(N^k).

Tùy chọn khác là bắt đầu với cùng một đường cơ sở, tính toán khoảng cách tối thiểu cho mỗi cặp và sau đó thử cải thiện nó. Giả sử bạn có một tập hợp con với khoảng cách tối thiểu là 10, bây giờ hãy thử một số với 11. Có thể dễ dàng thực hiện điều này bằng thuật toán tham lam - chọn mục đầu tiên trong chuỗi được sắp xếp sao cho khoảng cách giữa nó và mục trước lớn hơn - bằng với khoảng cách bạn muốn. Nếu bạn thành công, hãy thử tăng thêm, nếu bạn thất bại - không có tập con nào như vậy.

Giải pháp sau có thể nhanh hơn khi mảng lớn và k tương đối lớn, nhưng các phần tử trong mảng tương đối nhỏ. Nếu chúng bị ràng buộc bởi một số giá trị M, thuật toán này sẽ mất O(N*M) thời gian hoặc, với một cải tiến nhỏ, O(N*log(M)), trong đó N là kích thước của mảng.

Như Evgeny Kluev đề xuất trong câu trả lời của mình, cũng có giới hạn trên tốt trên khoảng cách tối đa theo cặp, có thể được sử dụng trong cả hai thuật toán này. Vì vậy, sự phức tạp của sau này thực sự là O(N*log(M/k)).

Answer 3

Tôi cho rằng thiết lập của bạn được đặt hàng. Nếu không, câu trả lời của tôi sẽ được thay đổi một chút.

Let's suppose you have an array X = (X1, X2, ..., Xn) 

Energy(Xi) = min(|X(i-1) - Xi|, |X(i+1) - Xi|), 1 < i <n 

j <- 1 
while j < n - k do 
    X.Exclude(min(Energy(Xi)), 1 < i < n) 
    j <- j + 1 
    n <- n - 1 
end while 

Answer 4

 
$length = length($array); 
sort($array); //sorts the list in ascending order 
$differences = ($array << 1) - $array; //gets the difference between each value and the next largest value 
sort($differences); //sorts the list in ascending order 
$max = ($array[$length-1]-$array[0])/$M; //this is the theoretical max of how large the result can be 
$result = array(); 
for ($i = 0; i < $length-1; $i++){ 
    $count += $differences[i]; 
    if ($length-$i == $M - 1 || $count >= $max){ //if there are either no more coins that can be taken or we have gone above or equal to the theoretical max, add a point 
     $result.push_back($count); 
     $count = 0; 
     $M--; 
    } 
} 
return min($result) 

Đối với những người phi mã: sắp xếp danh sách, tìm ra sự khác biệt giữa mỗi 2 yếu tố tuần tự, sắp xếp danh sách đó (theo thứ tự tăng dần), sau đó vòng qua nó tổng hợp các giá trị liên tục cho đến khi bạn hoặc vượt qua tối đa lý thuyết hoặc có đủ yếu tố còn lại; sau đó thêm giá trị đó vào mảng mới và tiếp tục cho đến khi bạn nhấn vào cuối mảng. sau đó trả về giá trị tối thiểu của mảng mới được tạo.

Đây chỉ là bản nháp nhanh. Trong nháy mắt, bất kỳ thao tác nào ở đây đều có thể được thực hiện trong thời gian tuyến tính (sắp xếp theo các kiểu sắp xếp).

Ví dụ, với 1, 4, 7, 100, và 200 và M = 3, ta có:

$differences = 3, 3, 93, 100 
$max = (200-1)/3 ~ 67 
then we loop: 
$count = 3, 3+3=6, 6+93=99 > 67 so we push 99 
$count = 100 > 67 so we push 100 
min(99,100) = 99 

Đó là một bài tập đơn giản để chuyển đổi này để các giải pháp thiết lập mà tôi để lại cho các người đọc (PS sau tất cả những lần đọc trong một cuốn sách, tôi luôn muốn nói điều đó: P)