Giải quyết các câu đố từ lộn xộn với python?

Question

Tôi có một câu đố chương trình thú vị dành cho bạn:

Bạn sẽ được cung cấp hai điều:

1. Một từ có chứa một danh sách các từ tiếng Anh đặt lại với nhau, ví dụ:

   word = "iamtiredareyou" 
   

2. Tập hợp con có thể:

   subsets = [ 
       'i', 'a', 'am', 'amt', 'm', 't', 'ti', 'tire', 'tired', 'i', 
       'ire', 'r', 're', 'red', 'redare', 'e', 'd', 'da', 'dar', 'dare', 
       'a', 'ar', 'are', 'r', 're', 'e', 'ey', 'y', 'yo', 'you', 'o', 'u' 
   ] 
   

Thách thức:

Level-1: tôi cần phải thực dụng tìm các thành viên trong subsets mà cùng nhau trong một trật tự sẽ làm cho "iamtiredareyou" tức ['i', 'am', 'tired', 'are', 'you']

Level-2: Chuỗi ban đầu có thể bao gồm một số ký tự phụ trong chuỗi không có trong tập hợp con. ví dụ. "iamtired12aareyou". Các subset được đưa ra là tương tự như trên, giải pháp sẽ tự động bao gồm tập con này ở đúng nơi trong mảng kết quả. tức là ['i', 'am', 'tired', '12a', 'are', 'you']

Tôi làm cách nào để thực hiện việc này?

Answer 1

Nói chung, thuật toán đệ quy sẽ thực hiện. Bắt đầu với việc kiểm tra tất cả các tập hợp con khi bắt đầu từ đã cho, nếu tìm thấy - thêm (chắp thêm) vào các giá trị tìm được và chấp nhận phần còn lại của từ và giá trị hiện tại. Hoặc nếu đó là phần cuối của chuỗi - in các giá trị được tìm thấy.

một cái gì đó như thế:

all=[] 
def frec(word, values=[]): 
    gobal all 
    if word == "": # got result. 
     all+=[values] 
    for s in subsets: 
     if word.startswith(s): 
      frec(word[len(s):], values+[s]) 

frec(word) 

lưu ý rằng có rất nhiều giải pháp khả thi từ các tập con gồm nhiều chuỗi một ký tự. Bạn có thể muốn tìm một số kết quả ngắn nhất. (13146 giải pháp ... sử dụng "all.sort (cmp = lambda x, y: cmp (len (x), len (y)))" để có được ngắn nhất)

Với mức 2 - bạn cần một vòng lặp nếu không có các tập hợp con nào phù hợp để thêm nhiều biểu tượng hơn vào giá trị tiếp theo (và đệ quy vào đó) cho đến khi kết hợp được tìm thấy.

all=[] 
def frec(word, values=[]): 
    global all 
    if word == "": # got result. 
     all+=[values] 
     return true 
    match = False 
    for s in subsets: 
     if word.startswith(s): 
      match = True 
      frec(word[len(s):], values+[s])  
    if not match:       
     return frec(word[1:], values+[word[0]]) 
frec(word) 

Điều này không cố gắng kết hợp các giá trị không tập hợp con thành một chuỗi.

Answer 2

tôi nghĩ rằng bạn nên làm bài tập lập trình của riêng bạn ....

Answer 3

Đối với các thách thức Level 1 bạn có thể làm điều đó recursively. Có lẽ không phải là giải pháp hiệu quả nhất, nhưng là giải pháp hiệu quả nhất:

word = "iamtiredareyou" 
subsets = ['i', 'a', 'am', 'amt', 'm', 't', 'ti', 'tire', 'tired', 'i', 'ire', 'r', 're', 'red', 'redare', 'e', 'd', 'da', 'dar', 'dare', 'a', 'ar', 'are', 'r', 're', 'e', 'ey', 'y', 'yo', 'you', 'o', 'u'] 

def findsubset(): 
    global word 

    for subset in subsets: 
     if word.startswith(subset): 
      setlist.append(subset) 
      word = word[len(subset):] 

      if word == "": 
       print setlist 
      else: 
       findsubset() 

      word = subset + word 
      setlist.pop() 

# Remove duplicate entries by making a set 
subsets = set(subsets) 
setlist = [] 
findsubset() 

Danh sách các tập con của bạn có bản sao trong đó - ví dụ: 'a' xuất hiện hai lần - vì vậy mã của tôi làm cho nó là set để xóa các mục trùng lặp trước khi tìm kiếm kết quả.

Answer 4

Nó không giống như tìm các hoán vị, nhưng với một số điều kiện?Giống như bạn bắt đầu thuật toán hoán vị (một đệ quy) bạn kiểm tra xem chuỗi bạn đã có khớp với ký tự X đầu tiên của từ tìm kiếm hay không, nếu có bạn tiếp tục đệ quy cho đến khi bạn tìm thấy toàn bộ từ, nếu không bạn sẽ quay trở lại.

Cấp 2 hơi ngớ ngẩn nếu bạn hỏi tôi, bởi vì sau đó bạn có thể viết bất cứ thứ gì làm từ "tìm được", nhưng về cơ bản nó sẽ giống như level1 với ngoại lệ là nếu bạn không thể tìm thấy substring trong danh sách của bạn, bạn chỉ cần thêm nó (thư bằng chữ cái, nghĩa là bạn có "tình yêu" và danh sách ['l', 'e'] bạn kết hợp 'l' nhưng bạn thiếu 'o' để bạn thêm nó và kiểm tra xem có các từ của bạn trong danh sách bắt đầu bằng chữ 'v' và khớp với từ của bạn được tìm thấy, chúng không có nghĩa là bạn thêm 'v' vào 'o', v.v.).

Và nếu bạn đang chán bạn có thể thực hiện một thuật toán genically, nó thực sự vui vẻ nhưng không thực sự hiệu quả.

Answer 5

Đây là một đệ quy, hiệu quả giải pháp Java:

private static void findSolutions(Set<String> fragments, String target, HashSet<String> solution, Collection<Set<String>> solutions) { 
    if (target.isEmpty()) { 
     solutions.add(solution); 
     return; 
    } 

    for (String frag : fragments) { 
     if (target.startsWith(frag)) { 
      HashSet<String> solution2 = new HashSet<String>(solution); 
      solution2.add(frag); 
      findSolutions(fragments, target.substring(frag.length()), solution2, solutions); 
     } 
    }  
} 

public static Collection<Set<String>> findSolutions(Set<String> fragments, String target) { 
    HashSet<String> solution = new HashSet<String>(); 
    Collection<Set<String>> solutions = new ArrayList<Set<String>>(); 
    findSolutions(fragments, target, solution, solutions); 
    return solutions; 
} 

Answer 6

Xin lỗi về việc thiếu đoạn lập trình, nhưng tôi muốn đề nghị lập trình năng động. Cấp độ tấn công 1 và cấp 2 cùng một lúc bằng cách cho mỗi từ một chi phí và thêm tất cả các ký tự đơn không xuất hiện dưới dạng các từ có chi phí cao. Vấn đề là sau đó tìm cách tách chuỗi thành các từ mang lại tổng chi phí thấp nhất.

Làm việc từ trái sang phải dọc theo trình tự, tại mỗi điểm làm việc và tiết kiệm giải pháp chi phí thấp nhất tới và bao gồm điểm hiện tại và độ dài của từ kết thúc giải pháp đó. Để tìm ra câu trả lời cho điểm tiếp theo trong chuỗi, hãy xem xét tất cả các từ đã biết là hậu tố của chuỗi. Đối với mỗi từ như vậy, hãy tính tổng chi phí tốt nhất bằng cách thêm chi phí của từ đó vào chi phí (đã được giải quyết) của giải pháp tốt nhất kết thúc ngay trước khi từ đó bắt đầu. Lưu ý tổng chi phí nhỏ nhất và độ dài của từ tạo ra nó.

Khi bạn có chi phí tốt nhất cho toàn bộ chuỗi, hãy sử dụng độ dài của từ cuối cùng trong chuỗi đó để tìm ra từ cuối cùng và sau đó quay lại số ký tự đó để kiểm tra câu trả lời và nhận từ ngay trước từ cuối cùng, v.v.