Member Avatar for beforetheyknew

Hi im still quite a terrible programmer, so some of this is just confirmation of stuff i think is right (and please correct me if i have the wrong idea!)

How would you program an anogram maker ? I was thinking of breaking up a String with substring, and then using the random number generator to re-allocate the letters randomly.

and how would you solve them ? so like if i typed in letters then clicked anagram, i imagine you would search through an indepedent text file but i dont know how you would test if letters all letters were present. (eg. lfgo would return golf, or fog etc).

Also you would have to use a file reader to get dictionary words into the program? yeah? would that mean I would have to independently re-write the dictionary or is there a simpler way of doing it? lol

Thank you guys!

  • 2 Contributors
  • 1 Reply
  • 378 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by BestJewSinceJC

Dani AI

Generated

separated two different problems: (a) producing a random scramble of the letters and (b) finding real dictionary words that can be formed from those letters. 's permutation-based approach works in theory, but generating all permutations grows factorially and becomes impractical for typical word sizes. A simpler, faster pattern is to preprocess the dictionary and test letter counts instead of enumerating every arrangement.

For quick random shuffles (uniformly), use Fisher–Yates rather than piecing substrings at random. Example (Python):

import random

def shuffle(s):
    a = list(s)
    random.shuffle(a)   # uses Fisher-Yates under the hood
    return ''.join(a)

For exact anagrams (all letters used), build a map from a canonical signature (sorted letters) to words. Lookup is then O(1) per query after load:

from collections import defaultdict

def build_map(path):
    M = defaultdict(list)
    with open(path, encoding='utf-8') as f:
        for w in (x.strip().lower() for x in f):
            if w.isalpha():
                M[''.join(sorted(w))].append(w)
    return M

# lookup: M['fglo'] -> ['golf', ...]

To find any words that can be formed from a subset of the supplied letters (e.g., "lfgo" -> "golf", "fog"), test letter counts rather than generating subsets. Python (Counter) or Java (int[26]) approaches work well; Java example:

public static boolean canForm(String pool, String word) {
    int[] cnt = new int[26];
    for (char c: pool.toLowerCase().toCharArray())
        if (c >= 'a' && c <= 'z') cnt[c - 'a']++;
    for (char c: word.toLowerCase().toCharArray()) {
        if (c < 'a' || c > 'z') return false;
        if (--cnt[c - 'a'] < 0) return false;
    }
    return true;
}

Notes and pitfalls: normalize case and strip punctuation; filter dictionary by reasonable lengths to cut work; for single interactive queries, scanning a 50–200k-word list with the count test is fast. For many repeated queries, precompute and store per-word frequency arrays or group words by length/signature to speed filtering.

Member Avatar for BestJewSinceJC

An obvious way to generate permutations of n is to generate values for the Lehmer code (possibly using the factorial number system representation of integers up to n!), and convert those into the corresponding permutations. However the latter step, while straightforward, is hard to implement efficiently, because it requires n operations each of selection from a sequence and deletion from it, at an arbitrary position; of the obvious representations of the sequence as an array or a linked list, both require (for different reasons) about n2/4 operations to perform the conversion. With n likely to be rather small (especially if generation of all permutations is needed) that is not too much of a problem, but it turns out that both for random and for systematic generation there are simple alternatives that do considerably better. For this reason it does not seem useful, although certainly possible, to employ a special data structure that would allow performing the conversion from Lehmer code to permutation in O(n logn) time.

You could try to do some research on what I found for you above and try to generate all possible permutations of your String. Then, you could use a dictionary as your text file and look up each permutation using a binary search. Binary search works basically like you'd think it would for searching a dictionary: start in the middle, if your word is higher than the word in the middle, throw out the bottom half of the dictionary. Then go to the middle of the remaining portion. Rinse & repeat.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.