Author Topic: Из заданных букв составить слова  (Read 13393 times)

0 Members and 6 Guests are viewing this topic.

Атеист

  • Guest
Re: Из заданных букв составить слова
« Reply #15 on: July 08, 2017, 09:40:16 PM »
Доброго времени суток)
Интересная тут у вас задачка. Мне тоже захотелось попробовать свои силы и написать скрипт. С условиями вроде всё понятно - они все находятся в файле "ГородаБуквы.txt", и все слова начинаются с заглавной буквы. На основе этого файла я сделал несколько фильтров, которые посчитал обязательными для поиска загаданных слов.
К сожалению точно угадать загаданные города у меня не получилось, но получился список городов, среди которых точно есть искомые. Другими словами - список из 40 городов удалось сократить до 9. Не велико достижение. :) И в этом списке, по причине простого везения, город Владивосток на 100% один из искомых (он единственный содержит букву "В"). На этом я и застрял. Если убрать из файла "ГородаБуквы.txt" набор букв "Владивосток" и повторить поиск, то ничего не меняется. Может кто подскажет решение, если оно вообще есть?
Файлы для теста во вложении.

[spoiler=Скрипт]
Code: (clickermann) [Select]
//=============================== Подготовка ================================//

LOGCLEAR

TFREADARR("ГородаБуквы.txt", $arr_chars_tmp)

$arr_chars_tmp_size = ARRSIZE($arr_chars_tmp)

$chars_string = ""

FOR($n = 0, $n < $arr_chars_tmp_size)
   
   $arr_chars_tmp[$n] = STRFILTER($arr_chars_tmp[$n], " ", 0)
   
   $char = STRCUT($arr_chars_tmp[$n], 1, 1)
   
   $charset = STRFILTER($arr_chars_tmp[$n], $char, 1)
   //
   IF($charset ! "")
      ARRPUSH($arr_chars, $charset)
      $chars_string = STRCONCAT($chars_string, $char)
   END_IF
   
   $charset = STRFILTER($arr_chars_tmp[$n], $char, 0)
   //
   IF($charset ! "")
      ARRPUSH($arr_chars, $charset)
      $chars_string = STRCONCAT($chars_string, STRCUT($charset, 1, 1))
   END_IF
   
END_CYC

$max_item_length = STRLEN($chars_string) // максимальная длина слова

//--------------------------------

TFREADARR("Города.txt", $arr_list)

$arr_list_size = ARRSIZE($arr_list)


//=============================== Поиск слов ================================//

FOR($n = 0, $n < $arr_list_size)
   
   $item_length = STRLEN($arr_list[$n])
   
   IF( ($item_length < $max_item_length + 1) & ($item_length ! 0) ) // длина слова подходящая
     
      IF(STRFILTER($arr_list[$n], $chars_string, 0) = "") // слово содержит только нужные символы
         
         FOR($i = 0, $i < $arr_chars_size)
           
            $chars_count = STRLEN($arr_chars[$i])
           
            IF(STRLEN(STRFILTER($arr_list[$n], $arr_chars[$i], 0)) < $item_length - $chars_count) // не верное количество одинаковых символов
               $i = $arr_chars_size
               $discard = 1 // слово будет отброшено
            END_IF
           
         END_CYC
         
         IF($discard = 0)
            LOGWRITE ($arr_list[$n]) // подходящее слово, прошедшее все фильтры
         ELSE
            UNDEFINE($discard)
         END_IF
         
      END_IF     
   END_IF   
END_CYC


HALT
[/spoiler]

[spoiler=В логе:]
Code: [Select]
21:34:26 Адлер
21:34:26 Алапаевск
21:34:26 Алдан
21:34:26 Александров
21:34:26 Александровск
21:34:26 Анапа
21:34:26 Балтийск
21:34:26 Братск
21:34:26 Владивосток
[/spoiler]

Vir

  • Зашел в гости
  • *
  • Posts: 12
    • View Profile
Re: Из заданных букв составить слова
« Reply #16 on: July 09, 2017, 12:08:08 AM »
Quote
Может кто подскажет решение, если оно вообще есть?
Перебрать все варианты составления 5 городов из 9 возможных. Что-то вроде:
Адлер Алапаевск Алдан Александров Александровск
Адлер Алапаевск Алдан Александров Анапа
Адлер Алапаевск Алдан Александров Балтийск
и т. д.
Дальше подбираем вариант, который можно собрать из набора букв.
9! / ((9 - 5)! * 5!) = 126 вариантов  (для справки: 5! - факториал числа, 1 * 2 * 3 * 4 * 5 = 120)
Да, не самый быстрый способ.
« Last Edit: July 09, 2017, 12:18:46 AM by Vir »

Атеист

  • Guest
Re: Из заданных букв составить слова
« Reply #17 on: July 09, 2017, 01:00:19 AM »
Перебрать все варианты составления 5 городов из 9 возможных. Что-то вроде:
Адлер Алапаевск Алдан Александров Александровск
Адлер Алапаевск Алдан Александров Анапа
Адлер Алапаевск Алдан Александров Балтийск
и т. д.
Дальше подбираем вариант, который можно собрать из набора букв.
9! / ((9 - 5)! * 5!) = 126 вариантов  (для справки: 5! - факториал числа, 1 * 2 * 3 * 4 * 5 = 120)
Да, не самый быстрый способ.

Что то ничего не понятно. :-[  Зачем перебирать все варианты составления 5 городов из 9 возможных? По условию мы не знаем сколько слов нужно найти и какие это слова.
И зачем "подбирать вариант, который можно собрать из набора букв", если все 9 слов выбраны скриптом как раз потому, что они гарантированно могут быть собраны из данного набора букв, который нам дан в файле "ГородаБуквы.txt"? Определенно я чего то не вкуриваю(.
Как я понимаю - нужно из 9 слов выкинуть лишние, или доказать, что каждое слово выбрано правильно. Так например в случае с городом Владивосток, как я писал выше.

Можно например подобрать слова, сумма букв которых будет равна сумме букв в файле "ГородаБуквы.txt", но там тоже могут быть варианты, хотя вроде как верняк. :) Может это имелось ввиду под фразой "Перебрать все варианты составления 5 городов из 9 возможных"?
Надо пробовать короче, а если что, придумаем что нибудь)).

Vir

  • Зашел в гости
  • *
  • Posts: 12
    • View Profile
Re: Из заданных букв составить слова
« Reply #18 on: July 09, 2017, 02:03:14 AM »
Quote
По условию мы не знаем сколько слов нужно найти и какие это слова.
Количество загаданных слов указано: 5.
Quote
Можно например подобрать слова, сумма букв которых будет равна сумме букв в файле "ГородаБуквы.txt"
Чтобы это сделать всё равно придётся перебрать все возможные варианты. Хотя этим можно отбросить часть вариантов, т. к. сравнить количество символов быстрее чем проверить можно ли составить слова из набора букв.
Список всех вариантов из 5 слов:
[spoiler]1. АдлерАлапаевскАлданАлександровАлександровск      Символов в строке: 43
2. АдлерАлапаевскАлданАлександровАнапа      Символов в строке: 35
3. АдлерАлапаевскАлданАлександровБалтийск      Символов в строке: 38
4. АдлерАлапаевскАлданАлександровБратск      Символов в строке: 36
5. АдлерАлапаевскАлданАлександровВладивосток      Символов в строке: 41
6. АдлерАлапаевскАлданАлександровскАнапа      Символов в строке: 37
7. АдлерАлапаевскАлданАлександровскБалтийск      Символов в строке: 40
8. АдлерАлапаевскАлданАлександровскБратск      Символов в строке: 38
9. АдлерАлапаевскАлданАлександровскВладивосток      Символов в строке: 43
10. АдлерАлапаевскАлданАнапаБалтийск      Символов в строке: 32
11. АдлерАлапаевскАлданАнапаБратск      Символов в строке: 30
12. АдлерАлапаевскАлданАнапаВладивосток      Символов в строке: 35
13. АдлерАлапаевскАлданБалтийскБратск      Символов в строке: 33
14. АдлерАлапаевскАлданБалтийскВладивосток      Символов в строке: 38
15. АдлерАлапаевскАлданБратскВладивосток      Символов в строке: 36
16. АдлерАлапаевскАлександровАлександровскАнапа      Символов в строке: 43
17. АдлерАлапаевскАлександровАлександровскБалтийск      Символов в строке: 46
18. АдлерАлапаевскАлександровАлександровскБратск      Символов в строке: 44
19. АдлерАлапаевскАлександровАлександровскВладивосток      Символов в строке: 49
20. АдлерАлапаевскАлександровАнапаБалтийск      Символов в строке: 38
21. АдлерАлапаевскАлександровАнапаБратск      Символов в строке: 36
22. АдлерАлапаевскАлександровАнапаВладивосток      Символов в строке: 41
23. АдлерАлапаевскАлександровБалтийскБратск      Символов в строке: 39
24. АдлерАлапаевскАлександровБалтийскВладивосток      Символов в строке: 44
25. АдлерАлапаевскАлександровБратскВладивосток      Символов в строке: 42
26. АдлерАлапаевскАлександровскАнапаБалтийск      Символов в строке: 40
27. АдлерАлапаевскАлександровскАнапаБратск      Символов в строке: 38
28. АдлерАлапаевскАлександровскАнапаВладивосток      Символов в строке: 43
29. АдлерАлапаевскАлександровскБалтийскБратск      Символов в строке: 41
30. АдлерАлапаевскАлександровскБалтийскВладивосток      Символов в строке: 46
31. АдлерАлапаевскАлександровскБратскВладивосток      Символов в строке: 44
32. АдлерАлапаевскАнапаБалтийскБратск      Символов в строке: 33
33. АдлерАлапаевскАнапаБалтийскВладивосток      Символов в строке: 38
34. АдлерАлапаевскАнапаБратскВладивосток      Символов в строке: 36
35. АдлерАлапаевскБалтийскБратскВладивосток      Символов в строке: 39
36. АдлерАлданАлександровАлександровскАнапа      Символов в строке: 39
37. АдлерАлданАлександровАлександровскБалтийск      Символов в строке: 42
38. АдлерАлданАлександровАлександровскБратск      Символов в строке: 40
39. АдлерАлданАлександровАлександровскВладивосток      Символов в строке: 45
40. АдлерАлданАлександровАнапаБалтийск      Символов в строке: 34
41. АдлерАлданАлександровАнапаБратск      Символов в строке: 32
42. АдлерАлданАлександровАнапаВладивосток      Символов в строке: 37
43. АдлерАлданАлександровБалтийскБратск      Символов в строке: 35
44. АдлерАлданАлександровБалтийскВладивосток      Символов в строке: 40
45. АдлерАлданАлександровБратскВладивосток      Символов в строке: 38
46. АдлерАлданАлександровскАнапаБалтийск      Символов в строке: 36
47. АдлерАлданАлександровскАнапаБратск      Символов в строке: 34
48. АдлерАлданАлександровскАнапаВладивосток      Символов в строке: 39
49. АдлерАлданАлександровскБалтийскБратск      Символов в строке: 37
50. АдлерАлданАлександровскБалтийскВладивосток      Символов в строке: 42
51. АдлерАлданАлександровскБратскВладивосток      Символов в строке: 40
52. АдлерАлданАнапаБалтийскБратск      Символов в строке: 29
53. АдлерАлданАнапаБалтийскВладивосток      Символов в строке: 34
54. АдлерАлданАнапаБратскВладивосток      Символов в строке: 32
55. АдлерАлданБалтийскБратскВладивосток      Символов в строке: 35
56. АдлерАлександровАлександровскАнапаБалтийск      Символов в строке: 42
57. АдлерАлександровАлександровскАнапаБратск      Символов в строке: 40
58. АдлерАлександровАлександровскАнапаВладивосток      Символов в строке: 45
59. АдлерАлександровАлександровскБалтийскБратск      Символов в строке: 43
60. АдлерАлександровАлександровскБалтийскВладивосток      Символов в строке: 48
61. АдлерАлександровАлександровскБратскВладивосток      Символов в строке: 46
62. АдлерАлександровАнапаБалтийскБратск      Символов в строке: 35
63. АдлерАлександровАнапаБалтийскВладивосток      Символов в строке: 40
64. АдлерАлександровАнапаБратскВладивосток      Символов в строке: 38
65. АдлерАлександровБалтийскБратскВладивосток      Символов в строке: 41
66. АдлерАлександровскАнапаБалтийскБратск      Символов в строке: 37
67. АдлерАлександровскАнапаБалтийскВладивосток      Символов в строке: 42
68. АдлерАлександровскАнапаБратскВладивосток      Символов в строке: 40
69. АдлерАлександровскБалтийскБратскВладивосток      Символов в строке: 43
70. АдлерАнапаБалтийскБратскВладивосток      Символов в строке: 35
71. АлапаевскАлданАлександровАлександровскАнапа      Символов в строке: 43
72. АлапаевскАлданАлександровАлександровскБалтийск      Символов в строке: 46
73. АлапаевскАлданАлександровАлександровскБратск      Символов в строке: 44
74. АлапаевскАлданАлександровАлександровскВладивосток      Символов в строке: 49
75. АлапаевскАлданАлександровАнапаБалтийск      Символов в строке: 38
76. АлапаевскАлданАлександровАнапаБратск      Символов в строке: 36
77. АлапаевскАлданАлександровАнапаВладивосток      Символов в строке: 41
78. АлапаевскАлданАлександровБалтийскБратск      Символов в строке: 39
79. АлапаевскАлданАлександровБалтийскВладивосток      Символов в строке: 44
80. АлапаевскАлданАлександровБратскВладивосток      Символов в строке: 42
81. АлапаевскАлданАлександровскАнапаБалтийск      Символов в строке: 40
82. АлапаевскАлданАлександровскАнапаБратск      Символов в строке: 38
83. АлапаевскАлданАлександровскАнапаВладивосток      Символов в строке: 43
84. АлапаевскАлданАлександровскБалтийскБратск      Символов в строке: 41
85. АлапаевскАлданАлександровскБалтийскВладивосток      Символов в строке: 46
86. АлапаевскАлданАлександровскБратскВладивосток      Символов в строке: 44
87. АлапаевскАлданАнапаБалтийскБратск      Символов в строке: 33
88. АлапаевскАлданАнапаБалтийскВладивосток      Символов в строке: 38
89. АлапаевскАлданАнапаБратскВладивосток      Символов в строке: 36
90. АлапаевскАлданБалтийскБратскВладивосток      Символов в строке: 39
91. АлапаевскАлександровАлександровскАнапаБалтийск      Символов в строке: 46
92. АлапаевскАлександровАлександровскАнапаБратск      Символов в строке: 44
93. АлапаевскАлександровАлександровскАнапаВладивосток      Символов в строке: 49
94. АлапаевскАлександровАлександровскБалтийскБратск      Символов в строке: 47
95. АлапаевскАлександровАлександровскБалтийскВладивосток      Символов в строке: 52
96. АлапаевскАлександровАлександровскБратскВладивосток      Символов в строке: 50
97. АлапаевскАлександровАнапаБалтийскБратск      Символов в строке: 39
98. АлапаевскАлександровАнапаБалтийскВладивосток      Символов в строке: 44
99. АлапаевскАлександровАнапаБратскВладивосток      Символов в строке: 42
100. АлапаевскАлександровБалтийскБратскВладивосток      Символов в строке: 45
101. АлапаевскАлександровскАнапаБалтийскБратск      Символов в строке: 41
102. АлапаевскАлександровскАнапаБалтийскВладивосток      Символов в строке: 46
103. АлапаевскАлександровскАнапаБратскВладивосток      Символов в строке: 44
104. АлапаевскАлександровскБалтийскБратскВладивосток      Символов в строке: 47
105. АлапаевскАнапаБалтийскБратскВладивосток      Символов в строке: 39
106. АлданАлександровАлександровскАнапаБалтийск      Символов в строке: 42
107. АлданАлександровАлександровскАнапаБратск      Символов в строке: 40
108. АлданАлександровАлександровскАнапаВладивосток      Символов в строке: 45
109. АлданАлександровАлександровскБалтийскБратск      Символов в строке: 43
110. АлданАлександровАлександровскБалтийскВладивосток      Символов в строке: 48
111. АлданАлександровАлександровскБратскВладивосток      Символов в строке: 46
112. АлданАлександровАнапаБалтийскБратск      Символов в строке: 35
113. АлданАлександровАнапаБалтийскВладивосток      Символов в строке: 40
114. АлданАлександровАнапаБратскВладивосток      Символов в строке: 38
115. АлданАлександровБалтийскБратскВладивосток      Символов в строке: 41
116. АлданАлександровскАнапаБалтийскБратск      Символов в строке: 37
117. АлданАлександровскАнапаБалтийскВладивосток      Символов в строке: 42
118. АлданАлександровскАнапаБратскВладивосток      Символов в строке: 40
119. АлданАлександровскБалтийскБратскВладивосток      Символов в строке: 43
120. АлданАнапаБалтийскБратскВладивосток      Символов в строке: 35
121. АлександровАлександровскАнапаБалтийскБратск      Символов в строке: 43
122. АлександровАлександровскАнапаБалтийскВладивосток      Символов в строке: 48
123. АлександровАлександровскАнапаБратскВладивосток      Символов в строке: 46
124. АлександровАлександровскБалтийскБратскВладивосток      Символов в строке: 49
125. АлександровАнапаБалтийскБратскВладивосток      Символов в строке: 41
126. АлександровскАнапаБалтийскБратскВладивосток      Символов в строке: 43[/spoiler]
Список вариантов, которые по количеству символов, соответствуют количеству символов из файла ГородаБуквы.txt (46 букв):
[spoiler]1. АдлерАлапаевскАлександровАлександровскБалтийск      Символов в строке: 46
2. АдлерАлапаевскАлександровскБалтийскВладивосток      Символов в строке: 46
3. АдлерАлександровАлександровскБратскВладивосток      Символов в строке: 46
4. АлапаевскАлданАлександровАлександровскБалтийск      Символов в строке: 46
5. АлапаевскАлданАлександровскБалтийскВладивосток      Символов в строке: 46
6. АлапаевскАлександровАлександровскАнапаБалтийск      Символов в строке: 46
7. АлапаевскАлександровскАнапаБалтийскВладивосток      Символов в строке: 46
8. АлданАлександровАлександровскБратскВладивосток      Символов в строке: 46
9. АлександровАлександровскАнапаБратскВладивосток      Символов в строке: 46[/spoiler]
Из 9 вариантов выбрать 1 уже проще.

Атеист

  • Guest
Re: Из заданных букв составить слова
« Reply #19 on: July 09, 2017, 01:00:47 PM »
Загаданные слова:
Адлер
Алапаевск
Александровск
Балтийск
Владивосток

Qwerry

  • Активный участник
  • ***
  • Posts: 117
    • View Profile
Re: Из заданных букв составить слова
« Reply #20 on: July 10, 2017, 06:28:51 PM »
Спасибо за интерес к теме и ваши наработки) Задача пока актуальна, просто последние дни была занята.
Атеист, интересный вариант. А я поленилась делать отдельно строку символов и массив под отдельные символы ($arr_chars). Сразу шла вторая проверка - совпадение по количеству, в итоге, работало дольше.
Vir, спасибо) Но вот вопрос, а как удалось получить все варианты по 5 городов из 9?
 
Как понимаю, здесь речь о сочетаниях элементов из Н по К. Удалось найти - короткий алгоритм (http://forum.sources.ru/index.php?showtopic=330364)   и с подробным объяснением, что и откуда берется (http://www.ie.tusur.ru/books/ProgDevelTech/Glava9/94.htm). Но перевести адекватно в код кликермана пока не вышло(

Атеист

  • Guest
Re: Из заданных букв составить слова
« Reply #21 on: July 10, 2017, 08:08:29 PM »
... как удалось получить все варианты по 5 городов из 9?
Получить 5 искомых городов из 9 пока не получилось. Это ответ на утверждение - "Количество загаданных слов указано: 5.", соответственно и названия городов нам известны из подсказки.
Мои достижения заканчиваются на том, что из файла "Города.txt" получен список из 9 городов, которые можно составить из имеющихся букв в файле "ГородаБуквы.txt". Так же было проверено, что количества одинаковых букв в файле "ГородаБуквы.txt" будет достаточно, чтобы собрать каждое из 9 слов в отдельности. Кстати, в моем скрипте есть ошибка в строке 33 (эта строка кода собиралась без учета дубликатов в переменной $chars_string и осталась такой после добавления фильтра дубликатов в строках 17 - 22), максимальная длина слова может быть больше.
Дальше всё только на уровне идей. Например можно выкинуть из списка девяти городов такие, которые содержат только одну букву в файле "ГородаБуквы.txt" и одновременно только одну букву в списке 9 городов. Это буквы "В" и "й". Соответственно города Владивосток и Балтийск. Стоит ли делать такой фильтр или нет непонятно. В другой задаче такой подход не сработает. Хотя такой фильтр неплохо бы иметь под рукой всегда. Выкинув 2 города из 9, мы укорачиваем строку $chars_string и при повторном использовании того же скрипта можем отфильтровать лишние города.
Или же лучше пойти путем, который предложил Vir - складывать слова, считать сумму символов и найти нужную комбинацию слов, которая должна быть равна сумме символов в файле "ГородаБуквы.txt"? Это безусловно нужно сделать, хотя такой подход тоже не всегда даст 100% результат.
Еще нужно определиться - известно ли нам количество искомых городов или нет, чтобы не путать друг друга.
Ситуация такая - изначально было N слов (каждое из которых написано с заглавной буквы).
В общем, видимо придется скомбинировать все идеи в одном скрипте, чтобы получился универсальный инструмент.

Qwerry

  • Активный участник
  • ***
  • Posts: 117
    • View Profile
Re: Из заданных букв составить слова
« Reply #22 on: July 10, 2017, 09:31:17 PM »
Еще нужно определиться - известно ли нам количество искомых городов или нет, чтобы не путать друг друга.
Количество искомых слов в принципе известно - оно равно количеству Заглавных букв в файле "ГородаБуквы.txt". Если задача содержала бы не города, слова всё равно писались бы с заглавной. Но вероятно мучить машину (вернее себя), заставляя ее отличать заглавные от строчных и высчитывать общее количество заглавных букв, не стоит.  Можно считать, что оно известно и заполняется человеком.
[spoiler] Для программного подсчета Заглавных самая первая из возникших (пусть и откровенно неадекватная) идея: воспользоваться тем, что KEYSTRING("str") печатает текст без учета регистра. Т.е. строка1 (с заглавными) всего из-за пары строчек кода (хотя и за относительно долгое время, т.к. стандартная задержка между нажатиями 30мс) может превратиться  в строку2 (тот же текст, но строчными). Создать строку3, содержащую лишь Заглавные буквы, и узнать ее длину не составит  труда. [/spoiler]
Что касается идей и пути решения - фильтр на единственную в своем роде букву отличная стратегия (в особенности, когда необходимо найти города своим умом), но с учетом возможности использовать быстродействие компьютера, этот способ вряд ли будет основным. Без перебора комбинаций слов все равно не обойтись.
Quote
В общем, видимо придется скомбинировать все идеи в одном скрипте, чтобы получился универсальный инструмент.
Я только ЗА!

P.S.:Всё-таки странный я человек: пока не пожалуюсь "у меня что-то не получается!" - решение найти не могу, стоит пожаловаться - так мозги потихоньку просыпаются, начинаю понимать свои ошибки. В общем, проблема с "перевести адекватно в код кликермана" несколько сдвинулась с мёртвой точки.;D

open_78

  • Активный участник
  • ***
  • Posts: 285
  • v4.13.014 x64
    • View Profile
Re: Из заданных букв составить слова
« Reply #23 on: July 10, 2017, 09:46:30 PM »
Считает и выводит количество заглавных букв в буфере обмена:
Code: (clickermann) [Select]
PRINT("Заглавных букв - ",STRLEN(STRFILTER(FROMCLIP(),"АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЭЮЯ",1)))
HALT

Атеист

  • Guest
Re: Из заданных букв составить слова
« Reply #24 on: July 10, 2017, 10:14:32 PM »
Количество искомых слов в принципе известно - оно равно количеству Заглавных букв в файле "ГородаБуквы.txt".
Об этом я действительно не подумал, каюсь. :-\  Но это делает проект не универсальным и одноразовым, что наверное еще хуже.

Vir

  • Зашел в гости
  • *
  • Posts: 12
    • View Profile
Re: Из заданных букв составить слова
« Reply #25 on: July 11, 2017, 02:33:11 AM »
Quote
Vir, спасибо) Но вот вопрос, а как удалось получить все варианты по 5 городов из 9?
Просто 5 вложенных циклов. Да, это не универсально, т. к. для другого количества слов придётся менять количество циклов. Надо будет посмотреть нормальный алгоритм.
Синтаксис кликермана не знаю, так что могу только схематично написать.
Чтобы было проще понять, будем считать что города это цифры от 1 до 9
Code: [Select]
arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}    // массив из слов
for i = 1, 9   // вместо 9 размер массива
   for j = i + 1, 9    // чтобы предыдущий город не повторялся, каждый следующий цикл начинается со следующего слова
       for k = j + 1, 9
           for l =  k + 1, 9 
               for m = l + 1, 9
                   log arr[i] arr[j] arr[k] arr[l] arr[m]    // получим все возможные варианты из 5 слов
               end
           end
       end
   end
end
Quote
Или же лучше пойти путем, который предложил Vir - складывать слова, считать сумму символов и найти нужную комбинацию слов, которая должна быть равна сумме символов в файле "ГородаБуквы.txt"? Это безусловно нужно сделать, хотя такой подход тоже не всегда даст 100% результат.
Вообще там остаётся только проверить можно ли составить из набора букв (46) строку из 46 букв. Т. е. копируем первый символ строки (строка из 5 городов), удаляем его из набора, копируем второй, удаляем из набора и т. д. Если какого символа в наборе не окажется, значит строка не подходит, проверяем следующую.

Атеист

  • Guest
Re: Из заданных букв составить слова
« Reply #26 on: July 11, 2017, 08:55:47 AM »
Вообще там остаётся только проверить можно ли составить из набора букв (46) строку из 46 букв. Т. е. копируем первый символ строки (строка из 5 городов), удаляем его из набора, копируем второй, удаляем из набора и т. д. Если какого символа в наборе не окажется, значит строка не подходит, проверяем следующую.
По моему это очень хорошая и верная идея, но это потребует на самом деле склеивать слова в строки. В подобных алгоритмах удобнее оперировать не самими данными из массива, а их индексами. В нашем случае это суммы букв, из которых состоят слова, то есть складывать (по большей части однозначные) цифры. Причем складывать при условии, что сумма не превысит 46. Если эти суммы отсортированы, то вычисление прерывается при первом превышении контрольной суммы 46, оставшиеся элементы не перебираются и начинается попытка собрать строку из других элементов. Но при таком маленьком объеме данных, потеря пары миллисекунд не существенна.

По поводу "получить все варианты по 5 городов из 9" - обсуждалось подобное здесь - http://crapware.aidf.org/forum/index.php?topic=2358.0
Тяжелая это вещь, либо действительно нужно найти/придумать другой алгоритм. Кстати, когда то я мусолил эту тему в голове недели две наверно, хотел придумать способ лучше, но так и не придумал... забыл. :)

Я все таки не поленился и попробовал найти нужные города после прохода своим скриптом. Первые одиночные буквы в файле "ГородаБуквы.txt" были "В" и "й", соответственно города Владивосток и Балтийск на 100% те что мы искали. После удаления из файла "ГородаБуквы.txt" символов "ВладивостокБалтийск" в нем появились еще одиночные буквы, которые указали на следующие искомые слова, с той же вероятностью 100%. Так все 5 городов были найдены, хотя и вручную. Знать заранее количество искомых городов не потребовалось. Написать такой алгоритм было бы наверно не сложно).

Qwerry

  • Активный участник
  • ***
  • Posts: 117
    • View Profile
Re: Из заданных букв составить слова
« Reply #27 on: July 11, 2017, 07:46:23 PM »
Доделала часть с сочетаниями)  Решила сразу по универсальному (почти) алгоритму делать. Скину, может кому-то тоже пригодится.
[spoiler]
Из недостатков - не позволяет работать со слишком большими множествами (Сперва максимум был Combine(25,13)=5,2 млн комбинаций, сейчас  всё переиграла и стало (75,20) = 803 167 998 497 864 960(комбинаций). Но это уже точно почти предел ;D
Code: (clickermann) [Select]
/////////////////составление создания  сочетаний из Н по М //////Qwerry///////
SUB(fact,$n1,$m1)    //пример - из 4 элементов по 2 fact(4,2)// дает $num=6 (комбинаций)
   If(($n1=0)^($m1=0)^($n1=$m1))
      $num=1
   Else
      $num= $m1+1
      For($i=1,$i<$n1-$m1)
         $num=$num*($m1+$i+1)/ ($n1-$m1-$i+1)
      END_CYC

   End_if
   //   Print("fact_num ",$m1," ",$n1, " = ",$num)
END_SUB
//
SUB(GenComb,$k2,$n2,$m2)
   UNDEFINE($v)
   $b=0
   $k= $k2
   $n=$n2
   $m= $m2
   
   While($n>0)
      SWITCH($m)
      CASE(0)
         For($I=0, $i<$n)
            ARRPUSH($V, 0)
         End_cyc
         $n=0
      CASE($n)
         For($I=0, $i<$n)
            ARRPUSH($V, 1)
         End_cyc
         $n=0
      DEFAULT
         fact($n-1,$m)
         $B=  $num
         
         If($k<$B+1)
            ARRPUSH($V, 0)
            Inc($n,-1)
         else
            ARRPUSH($V, 1)
            Inc($k,-$b)
            Inc($n,-1)
            Inc($m,-1)
         End_if
      END_SWITCH
   End_cyc
//   $res=" "                       ///для проверки
//   For($i=0,$i< ARRSIZE($v))
//      $res=STRCONCAT($res, " ",$v[$i])
//   End_Cyc
//   Print(11-$k2," вариант из ", $n2, " по ",$m2, " - ", $res)
////////преобразование вектора $V(К Из n по m) в числа///////////////////////////////////
UNDEFINE($var)
$numb=1
For($i=$n2, $i>0,-1)
   If($v[$n2-$i]=1)
      ARRPUSH($Var, $N2-$i) // Или же ARRPUSH($Var,$N2-$i+1), если не для Массива используем
   End_if
End_cyc
$result=$var[0]
For($b=1,$b<arrsize($var))
   $result=strconcat($result,$var[$b])
End_cyc
print($result)
END_SUB
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//

SUB(Combine, $par1, $par2) //   $par1>$par2
fact($par1,$par2)
print("комбинаций - ",$Num)
$count=  $Num

//   UNDEFINE($combo)
For($aa=$count,$aa>0,-1)
   GenComb($aa,$par1,$par2)
   // $var[_] - массив, содержащий вариант №   (элементы от [0] до  [$par2])
   // $result  - строчка, с сочетанием № aa 
//ARRPUSH($combo, $result)     - Массив с сочетаниями в лексикографическом порядке
End_cyc
END_SUB


$time=  $_ms
LogClear
Combine(5,3) // $par1>$par2

//Print(Arrsize( $combo))
Print("Time: ", $_ms-$time)
Halt
[/spoiler]

Поменяла фильтры - сперва проверка длины, дальше - сверка по буквам. В общем результат выглядит так.
[spoiler]
Code: [Select]
17:51:58 Исходные буквы - АААаааааБВвввдддеееиийккккклллллнооопррссссстт
17:51:58 Заглавных букв - 5
17:51:58 Список букв  АаБВвдеийклнопрст
17:51:58 31 из 40 - не подходит
17:51:58 9 - подходит!
17:51:58 Адлер, Алапаевск, Алдан, Александров, Александровск, Анапа, Балтийск, Братск, Владивосток
17:51:58 время: 166
17:51:58 комбинаций - 126
17:51:59 01468  -  П О Д Х О Д И Т   П О Л Н О С Т Ь Ю
17:51:59 АдлерАлапаевскАлександровскБалтийскВладивосток
17:51:59
17:52:01
17:52:01 ********************************************
17:52:01
17:52:01 Найден ответ:  АдлерАлапаевскАлександровскБалтийскВладивосток
17:52:01 время: 3305
Или если с более мягкими условиями (На случай неполного совпадения формы загаданного и имеющегося в словаре  слова) поиска, то так. С потенциальным отсутствием слова в словаре (правда для этого добавляла в словарь строчку с пробелами/подчеркиванием) - тоже в целом предлагает варианты.
Code: [Select]
17:58:49 Исходные буквы - АААаааааБВвввдддеееиийккккклллллнооопррссссстт
17:58:49 Заглавных букв - 5
17:58:49 Список букв  АаБВвдеийклнопрст
17:58:49 31 из 40 - не подходит
17:58:49 9 - подходит!
17:58:49 Адлер, Алапаевск, Алдан, Александров, Александровск, Анапа, Балтийск, Братск, Владивосток
17:58:49 время: 135
17:58:49 комбинаций - 126
17:58:50 Частично подходит АдлерАлапаевскАлданБалтийскВладивосток
17:58:50 Неиспользованные буквы: ервсскко
17:58:50
17:58:50 Частично подходит АдлерАлапаевскАлданБратскВладивосток
17:58:50 Неиспользованные буквы: левссккиой
17:58:50
17:58:50 Частично подходит АдлерАлапаевскАлександровБалтийскВладивосток
17:58:50 Неиспользованные буквы: ск
17:58:50
17:58:50 01468  -  П О Д Х О Д И Т   П О Л Н О С Т Ь Ю
17:58:50 АдлерАлапаевскАлександровскБалтийскВладивосток
17:58:50
17:58:53
17:58:53 ********************************************
17:58:53
17:58:53 Найден ответ:  АдлерАлапаевскАлександровскБалтийскВладивосток
17:58:53 время: 3557
[/spoiler]

В каком-то смысле программа готова. Всем огромное спасибо за идеи и помощь!
Правда, с тем, что задача может сильно  разрастаться (в той, которая подтолкнула к мысли об скрипте, было 20 слов, ну или если брать те же 5 городов, но из более полного списка) -  простым перебором не обойтись (особенно с учетом того, как сильно увеличивается число комбинаций буквально из-за 1-2 слов). Так  что в итоге нужно будет чередовать механизмы подбора слов (по уникальным буквам, как-то оценивать распространенность буквы (если в списке букв лишь 2 а и 15 о, то слова с А и без О  рассматриваются в последнюю очередь). Но это - по мере появления идей и возможностей)