저는 20자 미만의 영어 단어를 모두 생성하는 쉘 스크립트를 작성하려고 합니다. 무차별 대입 외에 이를 수행할 수 있는 정말 효율적인 방법이 있는지 의심됩니다. 분명히 이것은 많은 횡설수설을 생성할 것이지만, 상당한 시간 동안 범위를 계산할 수 있다면 전체 세트를 사용하여 인간 언어의 측면을 탐구할 수 있기를 바랍니다.
또한, 이것을 계산하는 방법을 아시거나 공간이 무엇인지 알려주시는 분이 계시다면 알고 싶습니다. 기본적인 조합이나 순열인 것 같은데 어느 것이 어느 것인지는 모르겠습니다. 26 글자. 20 또는 25 길이. 나는 25가 좋은 단어를 생각해내기에 충분한 복잡성을 제공한다고 확신하지만, 이로 인해 계산 노력이 크게 증가할 수밖에 없습니다. 이 시리즈가 aaaaaaadfsf 및 bungology가 될 것이라는 데는 의심의 여지가 없습니다.
답변1
/usr/share/words
실제로 모든 영어 단어가 포함된 이라는 파일이 있습니다 .
이 파일을 사용하여 모든 영어 단어를 찾고 단어를 특정 길이로 만들 수 있습니다. 이렇게 할 수 있습니다.
awk 'length <=20' /usr/share/words | wc -l
이 파일에는 479396개의 단어가 있습니다.
답변2
20자의 단어를 원하면 26개의 글자가 있습니다.
26^20 = 19928148895209409152340197376
가능성. 오늘날의 컴퓨터는 빠르지만 과연 충분히 빠를까요? 행운을 빌어요;)
답변3
보다 작은 단어를 찾고 있으므로 20 characters
여기에는 1, 2, 3 .. or 19 characters
더 긴 단어가 포함됩니다(영어에 19자 단어가 있는지 확실하지 않음). 그렇다면 총 가능성의 수는 26 19 + 26 18 + 26 17 .. + 26 1 입니다 .
이 문제를 해결하는 강력한 방법은 영어의 26개 알파벳을 모두 포함하는 목록을 만드는 것입니다. 그런 다음 루프 내에서 for i = 0; i < 20; i++
알파벳 배열의 26자를 사용하여 가능한 모든 길이의 단어를 만듭니다.i
재귀는 당신의 친구입니다.길이가 긴 단어가 있으면 이를 영어 단어를 정의하는 데 사용되는 i
모든 단어에 전달할 수 있습니다 . 예를 들어 slm이 언급했듯이 모음이 없는 단어는 존재할 수 없습니다.filtering rules
참고: 소위 글쓰기는 filtering rules
간단한 작업이 아닙니다. 예를 들어, 단어에 다음이 포함되어 있는지 확인하는 것은 매우 쉽지만 aieou
이 확인을 통과한다고 해서 단어를 찾았다는 의미는 아닙니다. 아직 멀었습니다.
이 폭력적인 방법은 얼마나 걸리나요?
지미가 소식을 전했습니다 26^20 = 19928148895209409152340197376 ~ 2e28
. 이제 귀하의 컴퓨터에 하나가 있고 quad core 1.5 GHz processor
귀하의 프로그램이 각 코어를 활용할 수 있다고 상상해보십시오 100%
. 그러면 1.5e9 x 4 = 6e9
잠시 후에 루프가 제공됩니다. 각 순열 자체는 순열별로 multiple CPU cycles
고려해야 합니다. 26 characters
그러나 이 숫자는 에 비해 사소하므로 수학을 단순하게 유지하려면 # of permutations
모든 순열이 필요하다고 말할 수 있습니다 6 instructions
(모든 명령이 필요함 ). 1 CPU cycle
마침내, 당신은 그것을 얻습니다 (6 instructions/permutation x 2e28 permutations)/(6e9 instructions/second) = (2e19 seconds) ~ 6.35e11 years
.