Kiểm tra nếu một danh sách các chuỗi có thể được xích

Question

Câu hỏi

Thực hiện một chức năng bool chainable(vector<string> v), trong đó có một tập hợp các chuỗi làm tham số và trả về true nếu họ có thể xích. Hai chuỗi có thể được xích nếu là người đầu tiên kết thúc với cùng một nhân vật thứ hai bắt đầu với, ví dụ:

ship->petal->lion->nick = true; 
ship->petal axe->elf = false; 

Giải pháp của tôi:

Logic của tôi là nếu nó thể kết nối sẽ chỉ là một sự khởi đầu và kết thúc không khớp. Vì vậy, tôi tạo danh sách bắt đầu và danh sách kết thúc. như vậy.

starts:s,p,l,n 
ends: p,l,n,k 

nếu tôi xóa các phần tử chung, danh sách phải chứa tối đa một mục. cụ thể là s và k. Nếu như vậy danh sách là chainable. Nếu danh sách là cyclic, danh sách cuối cùng sẽ trống.

Nhưng tôi nghĩ rằng tôi đang thiếu một số trường hợp ở đây,

EDIT: rồi rõ ràng tôi đã sai sót trong giải pháp của tôi. Chúng ta có thể kết luận thuật toán tốt nhất cho điều này?

Answer 1

Vấn đề là để kiểm tra xem một Eulerian path tồn tại trong đồ thị có hướng mà đỉnh được các chữ cái xảy ra như chữ cái đầu tiên hoặc cuối cùng của ít nhất một trong những các từ được cung cấp và các cạnh của nó là các từ được cung cấp (mỗi từ là cạnh từ chữ cái đầu tiên của nó đến chữ cái cuối cùng).

Một số điều kiện cần thiết cho sự tồn tại của con đường Euler trong đồ thị ví dụ:

1. Đồ thị phải được kết nối.
2. Tất cả các đỉnh có tối đa hai ngoại lệ đều có nhiều cạnh vào và ra tương đương nhau. Nếu các đỉnh đặc biệt tồn tại, có chính xác hai, một trong số chúng có một cạnh đi xa hơn so với các đầu vào, cái còn lại có thêm một cạnh tới hơn là đi ra.

Điều cần thiết là dễ thấy: Nếu đồ thị có đường dẫn Euler, mọi đường dẫn đó đáp ứng tất cả các đỉnh ngoại trừ đỉnh cô lập (không đi ra ngoài và cạnh tới). Bằng cách xây dựng, không có đỉnh cô lập trong biểu đồ đang được xem xét ở đây. Trong một đường dẫn Euler, mỗi lần một đỉnh được truy cập, ngoại trừ điểm bắt đầu và kết thúc, một cạnh đến và một cạnh đi được sử dụng, vì vậy mỗi đỉnh với ngoại lệ có thể có của đỉnh bắt đầu và kết thúc có nhiều cạnh đến và đi. Đỉnh bắt đầu có thêm một cạnh đi hơn so với đầu vào và đỉnh kết thúc một cạnh đến hơn trừ đi, trừ khi đường dẫn Euler là một chu trình, trong trường hợp đó tất cả các đỉnh có nhiều cạnh đến và đi đều nhau.

Điều quan trọng là các điều kiện này cũng đủ. Người ta có thể chứng minh rằng bằng cách cảm ứng về số lượng các cạnh.

đó cho phép để kiểm tra rất hiệu quả:

• kỷ lục tất cả các cạnh và đỉnh như thu được từ những lời
• sử dụng một cấu trúc đoàn find/thuật toán để đếm các thành phần kết nối của đồ thị
• kỷ lục indegree - outdegree cho tất cả các đỉnh

Nếu number of components > 1 hoặc có (ít nhất) một đỉnh với |indegree - outdegree| > 1 hoặc có m quặng hơn hai đỉnh với indegree != outdegree, các từ không phải là chuỗi, nếu không chúng là.

Answer 2

Dưới đây là một trường hợp thuật toán của bạn không hoạt động:

ship 
pass 
lion 
nail 

của bạn bắt đầu và kết thúc danh sách đều s, p, l, n, nhưng bạn không thể thực hiện một chuỗi đơn (bạn nhận được hai chuỗi - ship->pass và lion->nail) .

Tìm kiếm đệ quy có thể là tốt nhất - chọn từ bắt đầu (1), và cho mỗi từ có thể theo dõi (2), hãy cố giải quyết vấn đề nhỏ hơn khi tạo chuỗi bắt đầu bằng (2) chứa tất cả các từ ngoại trừ (1).

Answer 3

nếu bạn thay thế petal và lion với pawn và label, bạn vẫn còn có:
starts:s,p,l,n
ends: p,l,n,k

Bạn thuật toán quyết định thể kết nối của nó, nhưng họ thì không.
Vấn đề là bạn đang ngắt kết nối các chữ cái đầu tiên và cuối cùng của mỗi từ.

Thuật toán lập trình hoặc thuật toán động đệ quy cần giải quyết vấn đề này.

Answer 4

séc seperatedly cho "Có thể kết nối" và là "cylcic"

nếu nó là cyclic nó phải có thể kết nối đầu tiên. bạn có thể làm một cái gì đó như thế này:

if (IsChainable) 
{ 
    if (IsCyclic() { ... } 
} 

Lưu ý: Đó là trường hợp nếu bạn chỉ kiểm tra phần tử đầu tiên và cuối cùng của chuỗi cho "cylic".

Answer 5

Điều đó không giống với sự khét tiếng traveling salesman problem?

Nếu bạn có n chuỗi, bạn có thể tạo biểu đồ ra khỏi chúng, trong đó mỗi nút tương ứng với một chuỗi. Bạn xây dựng các cạnh theo cách sau:

• Nếu chuỗi (. Resp nút) a và b là thể kết nối, bạn giới thiệu một cạnh a -> b với trọng lượng 1.
• Đối tất cả unchainable dây (resp. Nút) a và b, bạn giới thiệu một cạnh a -> b với trọng lượng n.

Sau đó, tất cả các chuỗi của bạn có thể chuỗi (không lặp lại) nếu và chỉ khi bạn có thể tìm thấy tuyến đường TSP tối ưu trong biểu đồ có trọng số nhỏ hơn 2n.

Lưu ý: Vấn đề của bạn thực sự đơn giản hơn TSP, vì bạn luôn có thể chuyển chuỗi chuỗi thành TSP, nhưng không nhất thiết phải theo cách khác.

Answer 6

Điều này có thể được giải quyết bằng cách giảm xuống vấn đề đường dẫn Euler bằng cách xem xét đồ thị G với N (G) = Σ và E (G) = a->e cho các từ aWe.

Answer 7

Như phimuemue đã chỉ ra, đây là vấn đề về đồ thị. Bạn có một tập hợp các chuỗi (đỉnh), với các cạnh (hướng). Rõ ràng, biểu đồ phải là connected để có thể chuỗi - điều này rất dễ kiểm tra. Thật không may, các quy tắc ngoài điều này có một chút không rõ ràng:

Nếu chuỗi có thể được sử dụng nhiều lần, nhưng liên kết không thể, thì vấn đề là tìm một số Eulerian path. Đường dẫn Eulerian sử dụng từng cạnh một lần, nhưng có thể sử dụng các đỉnh nhiều lần.

// this can form a valid Eulerian path 
yard 
dog 
god 
glitter 

yard -> dog -> god -> dog -> glitter 

Nếu không thể sử dụng nhiều lần, thì vấn đề là tìm một số Hamiltonian path. Kể từ khi vấn đề đường dẫn Hamilton là NP-hoàn thành, không có giải pháp hiệu quả chính xác được biết đến. Tất nhiên, đối với n nhỏ, hiệu quả không thực sự quan trọng và giải pháp bạo lực sẽ hoạt động tốt.

Tuy nhiên, mọi thứ không hoàn toàn đơn giản, bởi vì tập hợp các biểu đồ có thể xảy ra làm đầu vào cho vấn đề này bị giới hạn. Ví dụ: sau đây là biểu đồ được chỉ dẫn hợp lệ (trong ký hiệu dot) (*).

digraph G { 
    alpha -> beta; 
    beta -> gamma; 
    gamma -> beta; 
    gamma -> delta; 
} 

Tuy nhiên, biểu đồ này không thể được xây dựng từ chuỗi sử dụng các quy tắc của trò chơi này: Kể từ alpha và gamma cả kết nối với beta, họ phải kết thúc với cùng một ký tự (giả sử rằng họ kết thúc với 'x'), nhưng gamma cũng kết nối với delta, vì vậy delta cũng phải bắt đầu bằng 'x'. Nhưng delta không thể bắt đầu bằng 'x', bởi vì nếu có, thì sẽ có cạnh alpha -> delta, không nằm trong biểu đồ gốc.

Do đó, đây là không hoàn toàn giống với vấn đề đường dẫn Hamilton, bởi vì tập hợp các yếu tố đầu vào bị hạn chế hơn. Có thể là một thuật toán hiệu quả tồn tại để giải quyết vấn đề chuỗi chuỗi ngay cả khi không có thuật toán hiệu quả tồn tại để giải quyết vấn đề đường dẫn Hamilton.

Nhưng ... Tôi không biết thuật toán đó là gì. Có lẽ một người nào khác sẽ đưa ra một giải pháp thực sự, nhưng trong thời gian đó, tôi hy vọng ai đó tìm thấy câu trả lời này thú vị.

(*) Nó cũng sẽ xảy ra có đường dẫn Hamilton: alpha -> beta -> gamma -> delta, nhưng điều đó không liên quan đến những gì sau.

Answer 8

Dưới đây là một chương trình đơn giản để làm điều này lặp đi lặp lại:

#include <string> 
#include <vector> 
#include <iostream> 

using std::vector; 
using std::string; 

bool isChained(vector<string> const& strngs) 
{ 
    if (strngs.size() < 2) return false;  //- make sure we have at least two strings 
    if (strngs.front().empty()) return false; //- make sure 1st string is not empty 

    for (vector<string>::size_type i = 1; i < strngs.size(); ++i) 
    { 
     string const& head = strngs.at(i-1); 
     string const& tail = strngs.at(i); 
     if (tail.empty()) return false; 
     if (head[head.size()-1] != tail[0]) return false; 
    } 

    return true; 
} 

int main() 
{ 
    vector<string> chained; 
    chained.push_back("ship"); 
    chained.push_back("petal"); 
    chained.push_back("lion"); 
    chained.push_back("nick"); 

    vector<string> notChained; 
    notChained.push_back("ship"); 
    notChained.push_back("petal"); 
    notChained.push_back("axe"); 
    notChained.push_back("elf"); 

    std::cout << (isChained(chained) ? "true" : "false") << "\n";  //- prints 'true' 
    std::cout << (isChained(notChained) ? "true" : "false") << "\n"; //- prints 'false' 

    return 0; 
}