Thuật toán để nhóm các từ đảo chữ cái

Question

Cho một tập các từ, chúng ta cần tìm các từ đảo chữ và hiển thị từng danh mục một mình bằng thuật toán tốt nhất.

đầu vào:

man car kile arc none like 

đầu ra:

man 
car arc 
kile like 
none 

Giải pháp tốt nhất Tôi đang phát triển hiện đang dựa trên một Hashtable, nhưng tôi đang suy nghĩ về phương trình để chuyển đổi từ đảo chữ vào giá trị số nguyên.

Ví dụ: man => 'm' + 'a' + 'n' nhưng điều này sẽ không cung cấp giá trị duy nhất.

Bất kỳ đề xuất nào?

---

Xem đoạn mã sau trong C#:

string line = Console.ReadLine(); 
string []words=line.Split(' '); 
int[] numbers = GetUniqueInts(words); 
for (int i = 0; i < words.Length; i++) 
{ 
    if (table.ContainsKey(numbers[i])) 
    { 
     table[numbers[i]] = table[numbers[i]].Append(words[i]); 
    } 
    else 
    { 
     table.Add(numbers[i],new StringBuilder(words[i])); 
    } 

} 

Vấn đề là làm thế nào để phát triển GetUniqueInts(string []) phương pháp.

Answer 1

Không quan tâm đến chức năng băm tùy chỉnh. Sử dụng hàm băm chuỗi bình thường trên bất kỳ nền tảng nào của bạn. Điều quan trọng là làm cho chìa khóa cho bảng băm của bạn ý tưởng của một "từ được sắp xếp" - nơi từ được sắp xếp theo chữ cái, do đó, "xe hơi" => "acr". Tất cả các đảo chữ cái sẽ có cùng một "từ được sắp xếp".

Chỉ cần có một băm từ "từ được sắp xếp" đến "danh sách các từ cho từ được sắp xếp".Trong LINQ này là vô cùng đơn giản: sử dụng

using System; 
using System.Collections.Generic; 
using System.Linq; 

class FindAnagrams 
{ 
    static void Main(string[] args) 
    { 
     var lookup = args.ToLookup(word => SortLetters(word)); 

     foreach (var entry in lookup) 
     { 
      foreach (var word in entry) 
      { 
       Console.Write(word); 
       Console.Write(" "); 
      } 
      Console.WriteLine(); 
     } 
    } 

    static string SortLetters(string original) 
    { 
     char[] letters = original.ToCharArray(); 
     Array.Sort(letters); 
     return new string(letters); 
    } 
} 

mẫu:

c:\Users\Jon\Test>FindAnagrams.exe man car kile arc none like 
man 
car arc 
kile like 
none 

Answer 2

Tôi không nghĩ rằng bạn sẽ tìm thấy bất cứ điều gì tốt hơn so với bảng băm có hàm băm tùy chỉnh (sắp xếp các chữ cái của từ trước khi băm).

Tổng số các chữ cái sẽ không bao giờ hoạt động, bởi vì bạn thực sự không thể tạo ra 'ac' và 'bb' khác nhau.

Answer 3

Bạn sẽ cần số nguyên lớn (hoặc một chút vector thực sự) nhưng sau có thể làm việc

sự xuất hiện đầu tiên của giao số bit mỗi chữ cái get cho bức thư đó, sự xuất hiện thứ hai nhận được số bit cho bức thư đó + 26.

Ví dụ

một # 1 = 1 b # 1 = 2 C# 1 = 4 một # 2 = 2^26 b # 2 = 2^27

Sau đó, bạn có thể tổng hợp chúng lại với nhau, để có được một giá trị duy nhất cho từ đó dựa trên các chữ cái của nó.

yêu cầu lưu trữ của bạn cho các giá trị từ sẽ là:

n * 26 bit

trong đó n là số lượng tối đa sự xuất hiện của bất kỳ thư lặp đi lặp lại.

Answer 4

Một phiên bản Python cho tiếng cười khúc khích:

from collections import defaultdict 
res = defaultdict(list) 
L = "car, acr, bat, tab, get, cat".split(", ") 

for w in L: 
    res["".join(sorted(w))].append(w) 

print(res.values()) 

Answer 5

tôi đã thực hiện trước khi điều này với một mảng đơn giản đếm lá thư, ví dụ:

unsigned char letter_frequency[26]; 

T hen lưu trữ trong bảng cơ sở dữ liệu cùng với mỗi từ. Các từ có cùng ký tự chữ 'chữ ký' là đảo chữ cái, và một truy vấn SQL đơn giản sau đó trả về tất cả các từ đảo chữ cái của một từ trực tiếp. Với một số thử nghiệm với một từ điển rất lớn, tôi không tìm thấy từ nào vượt quá số đếm tần số là 9 cho bất kỳ chữ cái nào, vì vậy chữ ký có thể được biểu diễn dưới dạng một chuỗi số 0..9 (Kích thước có thể là dễ dàng giảm đi một nửa bằng cách đóng gói thành byte dưới dạng hex, và tiếp tục giảm bằng cách mã hóa số nhị phân, nhưng tôi không bận tâm với bất kỳ điều này cho đến nay).

Đây là một hàm ruby ​​để tính chữ ký của một từ đã cho và lưu nó vào một Hash, trong khi loại bỏ các bản sao. Từ Hash sau tôi xây dựng một bảng SQL:

def processword(word, downcase) 
    word.chomp! 
    word.squeeze!(" ") 
    word.chomp!(" ") 
    if (downcase) 
    word.downcase! 
    end 
    if ($dict[word]==nil) 
    stdword=word.downcase 
    signature=$letters.collect {|letter| stdword.count(letter)} 
    signature.each do |cnt| 
     if (cnt>9) 
     puts "Signature overflow:#{word}|#{signature}|#{cnt}" 
     end 
    end 
    $dict[word]=[$wordid,signature] 
    $wordid=$wordid+1 
    end 
end 

Answer 6

tôi đã sử dụng một chương trình Gödel lấy cảm hứng từ:

Gán các số nguyên tố P_1 để P_26 để các chữ cái (trong bất kỳ trật tự, nhưng để có được giá trị băm smallish tốt nhất để cung cấp cho các chữ cái thông thường số nguyên tố nhỏ).

Tạo biểu đồ các chữ cái trong từ.

Sau đó, giá trị băm là sản phẩm của mỗi chữ cái được liên kết với số nguyên tố tăng lên đến tần số của nó. Điều này cho một giá trị duy nhất cho mọi đảo chữ cái. đang

Python:

primes = [2, 41, 37, 47, 3, 67, 71, 23, 5, 101, 61, 17, 19, 13, 31, 43, 97, 29, 11, 7, 73, 83, 79, 89, 59, 53] 


def get_frequency_map(word): 
    map = {} 

    for letter in word: 
     map[letter] = map.get(letter, 0) + 1 

    return map 


def hash(word): 
    map = get_frequency_map(word) 
    product = 1 
    for letter in map.iterkeys(): 
     product = product * primes[ord(letter)-97] ** map.get(letter, 0) 
    return product 

này khéo léo thay đổi vấn đề khó khăn của việc tìm kiếm subanagrams vào (hay còn được biết đến là khó khăn) vấn đề của Sacombank với số lượng lớn ...

Answer 7

Gán một số nguyên tố độc đáo để các chữ cái az

Lặp lại mảng từ của bạn, tạo ra một sản phẩm của số nguyên tố dựa trên các chữ cái trong mỗi từ.
Lưu trữ sản phẩm đó trong danh sách từ của bạn, với từ tương ứng.

Sắp xếp mảng, tăng dần theo sản phẩm.

Lặp lại mảng, thực hiện control break ở mọi thay đổi sản phẩm.

Answer 8

Trong C, tôi chỉ thực hiện băm sau đây về cơ bản hiện một bitmask 26 bit về việc liệu từ trong từ điển có một chữ cái cụ thể trong nó hay không. Vì vậy, tất cả các đảo chữ cái có cùng một băm. Hàm băm không tính đến các chữ cái lặp đi lặp lại, do đó sẽ có một số quá tải bổ sung, nhưng nó vẫn quản lý nhanh hơn so với thực thi perl của tôi.

#define BUCKETS 49999 

struct bucket { 
    char *word; 
    struct bucket *next; 
}; 

static struct bucket hash_table[BUCKETS]; 

static unsigned int hash_word(char *word) 
{ 
    char *p = word; 
    unsigned int hash = 0; 

    while (*p) { 
     if (*p < 97 || *p > 122) { 
      return 0; 
     } 
     hash |= 2 << (*p - 97); 
     *p++; 
    } 

    return hash % BUCKETS; 
} 

Xô quá tải được tạo và thêm dưới dạng danh sách được liên kết, v.v.Sau đó, chỉ cần viết một hàm đảm bảo rằng các từ khớp với giá trị băm có cùng độ dài và các chữ cái trong mỗi giá trị từ 1 đến 1 và trả về giá trị đó làm đối sánh.

Answer 9

Tôi sẽ tạo bản đồ dựa trên từ mẫu và phần còn lại của bảng chữ cái tôi sẽ không quan tâm.

Ví dụ nếu từ đó là "xe hơi" bảng băm của tôi sẽ như thế này: một, 0 b, MAX c, 1 d, MAX e, MAX ... .. r, 2 . Kết quả là bất kỳ số nào lớn hơn 3 sẽ coi là không khớp với

(điều chỉnh thêm ...) Và phương pháp so sánh của tôi sẽ so sánh tổng số băm trong tính toán băm. Nó sẽ không tiếp tục khi nó có thể xác định từ không bằng nhau.

public static HashMap<String, Integer> getHashMap(String word) { 
     HashMap<String, Integer> map = new HashMap<String, Integer>(); 
     String[] chars = word.split(""); 
     int index = 0; 
     for (String c : chars) { 
      map.put(c, index); 
      index++; 
     } 
     return map; 
    } 

    public static int alphaHash(String word, int base, 
      HashMap<String, Integer> map) { 
     String[] chars = word.split(""); 
     int result = 0; 
     for (String c : chars) { 
      if (c.length() <= 0 || c.equals(null)) { 
       continue; 
      } 
      int index = 0; 
      if (map.containsKey(c)) { 
       index = map.get(c); 
      } else { 
       index = Integer.MAX_VALUE; 
      } 
      result += index; 
      if (result > base) { 
       return result; 
      } 
     } 
     return result; 
    } 

phương thức Main

HashMap<String, Integer> map = getHashMap(sample); 
     int sampleHash = alphaHash(sample, Integer.MAX_VALUE, map); 
     for (String s : args) { 
       if (sampleHash == alphaHash(s, sampleHash, map)) { 
        System.out.print(s + " "); 
       } 
      } 

Answer 10

tôi sẽ không sử dụng băm vì nó thêm phức tạp thêm cho nhìn lên và cho biết thêm. Việc băm, sắp xếp và nhân lên tất cả sẽ chậm hơn so với giải pháp biểu đồ dựa trên mảng đơn giản với theo dõi duy nhất. Trường hợp xấu nhất là O (2n):

// structured for clarity 
static bool isAnagram(String s1, String s2) 
{ 
    int[] histogram = new int[256]; 

    int uniques = 0; 

    // scan first string 
    foreach (int c in s1) 
    { 
     // count occurrence 
     int count = ++histogram[c]; 

     // count uniques 
     if (count == 1) 
     { 
      ++uniques; 
     } 
    } 

    // scan second string 
    foreach (int c in s2) 
    { 
     // reverse count occurrence 
     int count = --histogram[c]; 

     // reverse count uniques 
     if (count == 0) 
     { 
      --uniques; 
     } 
     else if (count < 0) // trivial reject of longer strings or more occurrences 
     { 
      return false; 
     } 
    } 

    // final histogram unique count should be 0 
    return (uniques == 0); 
} 

Answer 11

Tham khảo có thể được tìm thấy trong cách sau:

1. Chiều dài của từ phải phù hợp.
2. Thực hiện việc thêm mỗi ký tự theo giá trị số nguyên. Số tiền này sẽ khớp nếu bạn thực hiện tương tự trên đảo chữ cái.
3. Thực hiện phép nhân của từng ký tự theo giá trị số nguyên. Giá trị được đánh giá sẽ khớp nếu bạn thực hiện tương tự trên đảo chữ cái.

Vì vậy, tôi đã nghĩ qua ba lần xác thực, chúng tôi có thể tìm thấy đảo chữ cái. Đúng nếu tôi sai.

---

Ví dụ: abc cba

Chiều dài của cả hai từ là 3.

Sum ký tự riêng lẻ cho cả hai từ là 294.

Prod ký tự riêng lẻ cho cả hai từ là 941.094.

Answer 12

Phiên bản JavaScript. sử dụng băm.

Thời gian phức tạp: 0 (nm), trong đó n là số từ, m là chiều dài của từ

var words = 'cat act mac tac ten cam net'.split(' '), 
    hashMap = {}; 

words.forEach(function(w){ 
    w = w.split('').sort().join(''); 
    hashMap[w] = (hashMap[w]|0) + 1; 
}); 

function print(obj,key){ 
    console.log(key, obj[key]); 
} 

Object.keys(hashMap).forEach(print.bind(null,hashMap)) 

Answer 13

Chỉ muốn thêm giải pháp python đơn giản, thêm vào các câu trả lời hữu ích khác:

def check_permutation_group(word_list): 
    result = {} 

    for word in word_list: 
     hash_arr_for_word = [0] * 128 # assuming standard ascii 

     for char in word: 
      char_int = ord(char) 
      hash_arr_for_word[char_int] += 1 

     hash_for_word = ''.join(str(item) for item in hash_arr_for_word) 

     if not result.get(hash_for_word, None): 
      result[str(hash_for_word)] = [word] 
     else: 
      result[str(hash_for_word)] += [word] 

return list(result.values()) 

đang

Answer 14

python:

line = "man car kile arc none like" 
hmap = {} 
for w in line.split(): 
    ws = ''.join(sorted(w)) 
    try: 
    hmap[ws].append(w) 
    except KeyError: 
    hmap[ws] = [w] 

for i in hmap: 
    print hmap[i] 

đầu ra:

0.123.

['car', 'arc'] 
['kile', 'like'] 
['none'] 
['man']