Python: स्ट्रिंग निर्माण के लिए न्यूनतम तत्वों का संयोजन खोजना

Python में दी गई सूची से न्यूनतम संख्या में तत्व चुनकर, उनके वर्णों से लक्ष्य स्ट्रिंग बनाना संभव है या नहीं जांचना। यह एक सेट कवर / संयोजन खोज समस्या है।

समस्या

सूची: ["python", "is", "fun", "to", "learn"]

लक्ष्य: "onis"

न्यूनतम कितने तत्व चाहिए जिनके वर्णों से "onis" बने?

उत्तर: 2 ("python" में o,n,i,s और "is" में i,s - लेकिन "python" अकेले ही पर्याप्त है!)

मूल लेख का दृष्टिकोण (कॉम्बिनेशन ब्रूट-फोर्स)

from itertools import combinations

my_list = ["python", "is", "fun", "to", "learn"]
my_target_str = "onis"
print("सूची:", my_list)
print("लक्ष्य:", my_target_str)

my_result = -1
target_set = set(my_target_str)
found = False

for r in range(len(my_list) + 1):
    for combo in combinations(my_list, r):
        # संयोजन के सभी वर्णों को मिलाएं
        combined_chars = set(''.join(combo))
        if target_set.issubset(combined_chars):
            my_result = r
            found = True
            break
    if found:
        break

print(f"न्यूनतम तत्व: {my_result}")

आउटपुट

सूची: ['python', 'is', 'fun', 'to', 'learn']
लक्ष्य: onis
न्यूनतम तत्व: 1

नोट: मूल लेख का आउटपुट 2 था, लेकिन सही उत्तर 1 है

"python" में o, n, i, s सभी वर्ण मौजूद हैं, इसलिए केवल 1 तत्व काफी है। मूल लेख में लॉजिक त्रुटि थी।

सही और कुशल दृष्टिकोण

1. लालची दृष्टिकोण (Greedy - अनुमानित)

def min_elements_greedy(words, target):
    """लालची: सबसे अधिक नए वर्ण कवर करने वाला शब्द चुनें"""
    target_set = set(target)
    covered = set()
    selected = []
    remaining_words = list(words)
    
    while covered != target_set and remaining_words:
        # सबसे अधिक नए वर्ण कवर करने वाला शब्द खोजें
        best_word = max(remaining_words, key=lambda w: len(set(w) & (target_set - covered)))
        new_chars = set(best_word) & (target_set - covered)
        if not new_chars:
            break  # प्रगति नहीं
        covered |= new_chars
        selected.append(best_word)
        remaining_words.remove(best_word)
    
    return len(selected) if covered == target_set else -1, selected

print("लालची:", min_elements_greedy(my_list, "onis"))

2. BFS (सटीक न्यूनतम, छोटे इनपुट के लिए)

from collections import deque

def min_elements_bfs(words, target):
    """BFS से सटीक न्यूनतम खोजें"""
    target_set = set(target)
    word_sets = [set(w) for w in words]
    
    # State: (covered_set, used_indices_tuple)
    queue = deque([(frozenset(), ())])
    visited = set([frozenset()])
    
    while queue:
        covered, used = queue.popleft()
        if covered == target_set:
            return len(used), [words[i] for i in used]
        
        for i, wset in enumerate(word_sets):
            if i not in used:
                new_covered = covered | (wset & target_set)
                new_used = used + (i,)
                if new_covered not in visited:
                    visited.add(new_covered)
                    queue.append((new_covered, new_used))
    
    return -1, []

print("BFS:", min_elements_bfs(my_list, "onis"))

3. डायनामिक प्रोग्रामिंग (बिटमास्क, छोटे वर्ण सेट के लिए)

def min_elements_dp(words, target):
    """बिटमास्क DP - वर्ण सेट छोटा हो (≤20) तो तेज़"""
    # लक्ष्य वर्णों को इंडेक्स मैप करें
    unique_chars = list(set(target))
    char_to_bit = {c: i for i, c in enumerate(unique_chars)}
    target_mask = (1 << len(unique_chars)) - 1
    
    # प्रत्येक शब्द का बिटमास्क
    word_masks = []
    for w in words:
        mask = 0
        for c in set(w) & set(target):
            mask |= 1 << char_to_bit[c]
        if mask:
            word_masks.append(mask)
    
    # DP: dp[mask] = न्यूनतम शब्द
    INF = float('inf')
    dp = [INF] * (1 << len(unique_chars))
    dp[0] = 0
    
    for wmask in word_masks:
        for mask in range(target_mask, -1, -1):
            if dp[mask] != INF:
                new_mask = mask | wmask
                dp[new_mask] = min(dp[new_mask], dp[mask] + 1)
    
    return dp[target_mask] if dp[target_mask] != INF else -1

print("DP:", min_elements_dp(my_list, "onis"))

व्यावहारिक उपयोग: शब्द खेल, स्क्रैबल सहायक

def scrabble_helper(tiles, dictionary):
    """टाइल्स से बन सकने वाले शब्द खोजें"""
    tile_set = set(tiles)
    valid = []
    for word in dictionary:
        if set(word).issubset(tile_set):
            # आवृत्ति भी जांचें
            from collections import Counter
            if all(Counter(word)[c] <= Counter(tiles)[c] for c in word):
                valid.append(word)
    return sorted(valid, key=len, reverse=True)

# टेस्ट
tiles = list("pythonisfun")
dictionary = ["python", "is", "fun", "to", "learn", "on", "in", "no", "tip", "hot"]
print("स्क्रैबल शब्द:", scrabble_helper(tiles, dictionary))

सारांश