가능한 단어를 찾기위한 정규식 (스크래블 스타일)

저는 개발중인 스크래블과 같은 게임에 스트레스 테스트를 실행하기 위해 "스크래블 해법"을 만들려고합니다. ~ 200.000 단어를 포함하는 데이터베이스가 있고 데이터베이스의 단어와 함께 제공된 스크래블 타일을 일치시키는 방법을 찾고 있습니다.가능한 단어를 찾기위한 정규식 (스크래블 스타일)

예 :

Given tiles: A, P, E, F, O, L, M 

Result: APE, POLE, PALE, MOLE, PAL...

이 정규 표현식 간단한 SELECT 문을 사용하여 수 있습니까? 가능한 경우 특정 위치에 문자를 추가하고 최대/최소 길이를 결정할 수 있습니다.

나는이 질문을 만든 의미 : 내 눈을 인터넷 검색을 봤는데

희망 그러나 나는 내가 무엇을 찾고 찾을 수 없습니다. 누구나 아이디어있어?

감사합니다. :)

출처

2011-09-01 digi

흠, 그렇지 않을 수도 있습니다. regex없이 MySQL-db에서 이것을 얻을 수있는 다른 방법이 있습니까? – digi

관계형 데이터베이스에 단어를 저장하는 것이 좋지만 문자 조합을 찾기 위해 메모리에서보다 효율적인 데이터 구조로로드하는 것이 좋습니다. –

네, [Trie] (http://en.wikipedia.org/wiki/Trie)를 사용해야하는 것 같습니다. –

정규식 문제와 비슷하지 않습니다. 기존 타일의 문자 조합을 모두 생성 한 다음 IN 절을 사용하여 SELECT 문을 실행하는 것이 더 나을 것이라고 생각합니다. 타일 예를 들어 :

A, P, E

당신의 SELECT 절은

당신은 당신의 테이블에서 유효한 단어의 목록을 얻을 것이다됩니다.

출처

2011-09-01 09:03:43

좋습니다! 생각해 보면, 7 타일 이상으로는 느려지지 않을까요? – digi

7 개의 타일로 7 개 있습니다! = 5040 조합; 예, 약간 느릴 수 있습니다. 그러나 애플리케이션을 테스트하는 데만 이것을 사용한다면 성능이 가장 큰 걱정거리는 아닙니다. –

그게 사실이야, 내가 한 번 줄거야 :) 고마워 – digi

이 경우 정규 표현식이 도움이되지 않습니다. 혼자서 가능한 단어를 만들어야합니다.

문제는 가능한 문자 수에 제한이 있으며 정규 표현식에서 해당 정보를 인코딩 할 수 없다는 것입니다. 각 문자를 무한대로 제공한다면 [APEFOI]*과 같은 정규식을 사용할 수 있습니다.

가능한 모든 단어를 직접 열거해야합니다. 구현 방법은 사용하는 언어에 따라 다르지만 가장 좋은 방법은 next_permutation 함수 또는 모든 순열을 열거하는 함수 일 수 있습니다. (파이썬 같은 의사 코드) 간단한 (약간 비효율적) 구현은 다음과 같습니다 그 시점 words에서

words = [] 
for permutation in permutations(letters): # enumerate all character orders 
    for i in range(1, len(permutation)): # enumerate all lengths of words 
    words.append(letters[:i])    # append to candidate set

당신이 다음 SELECT ... IN 성명에서 사용하는 모든 후보 단어가 포함됩니다.

가장 효율적인 방법은 아니지만 시작하기에 충분히 실용적이어야합니다.

출처

2011-09-01 09:14:24 Peteris

올바른 방향으로 나를 가리켜 주셔서 감사합니다! – digi

가능한 단어를 찾기위한 정규식 (스크래블 스타일)

답변

관련 문제