В поисках панграмм [excel, vba]

Узнай цену своей работы

Формулировка задачи:

ПРИВЕТСТВИЕ ЧЕГО МЫ ХОТИМ? На входе имеем базу слов, на выходе – все возможные по условиям панграммы. УСЛОВИЯ 1. Панграммы ищем для n букв (первостепенно – 33). 2. Все буквы в конечном наборе слов предложении встречаются ровно по 1 разу. 3. Исходная база содержит слова с повторяющимися буквами и/или всякими ненужными символами (какими конкретно – не известно). МОЙ ВКЛАД 1. Нашел формулу массива для первоначальной сортировки базы: {=ИЛИ((ДЛСТР(A2)-ДЛСТР(ПОДСТАВИТЬ(СТРОЧН(A2);СИМВОЛ(СТРОКА($1:$255));"")))>1)} Для слов с повторяющимися буквами выдает ИСТИНА. Далее сортируем, все строки с ИСТИНА в расход, оставляем одни только ЛОЖИ. 2. Нашел макрос на очищение нашей уже обрезанной базы от всякой нечисти - достаточно указать список лишних символов. Проблема: база большая, какой там конкретно мусор – не известно. Искал макрос который бы выводил список всех символов (по 1 шт), имеющихся на листе, не нашел. 3. Подумал над алгоритмом для работы с результирующей базой. ВОЗМОЖНЫЙ АЛГОРИТМ 1. Выводим все буквы слова функцией ПСТР. 2. Создаем двоичный код каждого слова функцией СЧЁТЕСЛИ. 3. Переводим в десятичную систему счисления, поочередно умножая на 2^m (m<33) и затем суммируя. Можно, конечно, объединить все 0 и 1 в громоздкое 33-ёхзначное число, которое потом перегнать функцией ДВВДЕС. Имеем столбец #1 с.. назовем это численной записью числа. 4. Сортируем базу слов по столбцу #1. Имеем численную запись чисел по возрастанию/убыванию. 5. Моя остановочка. Дело за малым – научиться выделять из столбца #1 диапазон слов с разными буквами, сумма численных значений которых равна (2^33)-1 = 8589934591 (для 33-ёх букв, не говоря уже о количестве вариаций для 32, 31 и т.д.) ЛЁД ТРОНУЛСЯ Нашел такую весчь, называется подбор слагаемых под нужную сумму. Является частным случаем «задачи о рюкзаке». Наиболее оптимальные на мой беглый взгляд алгоритмы обитают тута (http://www.excelworld.ru/forum/10-5196-1). Вот если бы эту штуку как-то применить в нашей задаче. Описанный мною выше возможный алгоритм можно упростить до записи слов в двоичном коде. Далее: 1. Берем первое слово, сверяем с каждым на наличие одинаковых букв (единичек). Отбираем массив #1(1) слов с буквами, которых нет в нашем первом слове. 2. Берем первое слово из массива #1(1), сверяем с каждым из массива #1(1) на наличие одинаковых букв (единичек). Отбираем массив #2(1) слов с буквами, которых нет в нашем первом слове из массива #1(1). 3. Повторяем операцию до тех пор, пока конечный массив не превратится в слово. Суммируем двоичный код получившейся выборки и проверяем на равенство 11…11 (33 шт). 4. Возвращаемся на массив уровнем выше (предпоследний), берем оттуда второе слово и делаем все то же самое (опускаемся вниз, проверяем на равенство новую выборку). Если слов в нем больше двух, повторяем операцию с третьим и так далее. 5. Продолжаем последовательно подниматься до массива #1(1), где выбираем уже второе слово, вновь опускаемся до конечного «массива» (одно слово), вновь последовательно поднимаемся и опускаемся; возвратившись в массив #1(1), берем третье слово и так далее. 6. Проверив все слова из массива #1(1), возвращаемся в исходную базу, берем 2 слово, получаем массив #1(2) и работаем с ним аналогично. Перевод в десятичную СС – это просто сокращение записи. Можно назначить буквам «вес», например 1-33 и начать искать слагаемые под сумму 33*(33+1)/2 = 561, но т.к. они разнятся всего на единицу, ложных вариантов будет как минимум 90%. Можно назначить первой букве вес 10^-16, 17-ой – 1, последней – 10^16. В промежутке известно что. Ложные варианты сократятся на порядок. 10 можно заменить и на 100, и на 1000, но я не уверен, будет ли алгоритм подбора слагаемых под сумму корректно обрабатывать такие данные. По сути, от двоичного кодирования, как и от дальнейших преобразований, можно отказаться и работать напрямую с буквами. Не говоря уже о возможности существования варианта, где для сравнения 2-х слов на наличие одинаковых букв достаточно, 2-х ячеек, в которых, собственно, и записаны эти слова. Еще нашел макросы на расположение букв в слове в алфавитном порядке. Модернизированную таким образом базу можно отсортировать в алфавитном порядке, имеем, таким образом, 33 группы. Далее можно сгруппировать слова по наличию сочетаний АБ – ЮЯ (528), АБВ – ЭЮЯ (5456), АБВГ – ЫЭЯЮ (40920) и т.д. (исходя из формулы N!/((N – M*K)!*((K!)^M)), и уже это использовать как условие для запрета совмещения тех или иных слов. Если все гораздо проще, то да простит меня Оккам!

Решение задачи: «В поисках панграмм [excel, vba]»

textual
Листинг программы
  1. Option Base 1
  2. Dim Ch
  3. Sub Pangramma_na_baze()
  4.     Const MaxKolPangramm = 1 ' Чтобы не набирать огромное число комбинаций слов для среднего числа букв
  5.    Dim i&, ii%, j%, k%, kk&, A, B, PanKol%, strokaVhod$, KolSlov&, S$, Z$, Novoe As Boolean
  6.     Dim KolSlovStolb&(10), Pangramma$(MaxKolPangramm), Predlojenie$(16), SlovoRow&(0 To 16), SlovoCol%(0 To 16)
  7.     Dim Obrazec() As Boolean, OstatokObr() As Boolean, OstatokObrOld(), Tek() As Boolean
  8.     ReDim Obrazec(33), OstatokObr(33), OstatokObrOld(0 To 33), Tek(33)
  9.     strokaVhod = "абвгдеёжзийклмнопрстуфхцчшщъыьэюя" ' "ад и ёж" '"а я ёж" ' "абвгдеёжзя" '"абвгдеёжзийклмнопрстуфхцчшщъыьэюя"
  10.    strokaVhod = LCase(strokaVhod) ' работаем со строчными буквами
  11.    ' Цифрограмма слова это массив от 1до 33, 1-32 = а-я, 33=ё . True если есть буква в слове.
  12.    Cifrogramma strokaVhod, Obrazec
  13.     'Номера позиций в цифрограмме в порядке понижения частотности букв
  14.    ' о е а и н т с р в л к м д п у я ы ь г з б ч й х ж ш ю ц щ э ф ъ ё
  15.    Ch = Array(15, 6, 1, 9, 14, 19, 18, 17, 3, 12, 11, 13, 5, 16, 20, 32, 28, 29, 4, 8, 2, 24, 10, 22, 7, 25, 31, 23, 26, 30, 21, 27, 33)
  16.     With Worksheets("Baza")
  17.         ' Массив с базой слов. Номер столбца от 1 до 10 равен числу букв в словах. Каждый столбец упорядочен по алфавиту.
  18.        A = .UsedRange.Value
  19.         For j = 1 To 10
  20.             KolSlovStolb(j) = .Cells(.Rows.Count, j).End(xlUp).Row
  21.         Next
  22.     End With
  23.     ReDim B(UBound(A), 10) ' Массив массивов цифрогамм слов из базы
  24.    For j = 1 To 10
  25.         For i = 1 To KolSlovStolb(j)
  26.             ReDim Tek(33)
  27.             Cifrogramma A(i, j), Tek
  28.             B(i, j) = Tek
  29.         Next i
  30.     Next j
  31.     '--- перебор слов в базе------------
  32.    For PanKol = 1 To MaxKolPangramm
  33.         OstatokObr = Obrazec
  34.         KolSlov = 0
  35.         Erase Predlojenie
  36.         'For k = 1 To 16: SlovoRow(k) = 0: SlovoCol(k) = 10: Next k
  37.        '##############################################             оптимизация для 33 букв
  38.        For k = 1 To 16: SlovoRow(k) = 0: SlovoCol(k) = 5: Next k ' оптимизация для 33 букв
  39.        KolSlovStolb(1) = 0: KolSlovStolb(2) = 0            ' оптимизация для 33 букв
  40.        '############################################## оптимизация для 33 букв
  41.        If PanKol = 1 Then SlovoRow(0) = 0: SlovoCol(0) = SlovoCol(1)
  42.         Do
  43.             For j = SlovoCol(KolSlov) To 1 Step -1
  44.                 ii = IIf(j = SlovoCol(KolSlov), SlovoRow(KolSlov) + 1, 1)
  45.                 For i = ii To KolSlovStolb(j)
  46.                     If EstVObrazce(OstatokObr, B(i, j)) Then
  47.                         ObrazecMinusSlovo OstatokObr, B(i, j), Tek
  48.                        ' Stop '+++++++++++
  49.                        SlovoRow(KolSlov) = i
  50.                         SlovoCol(KolSlov) = j
  51.                         OstatokObrOld(KolSlov) = OstatokObr
  52.                         OstatokObr = Tek
  53.                         KolSlov = KolSlov + 1
  54.                         Predlojenie(KolSlov) = A(i, j)
  55.                         If NeOstalosBukv(OstatokObr) Then
  56.                             S = ""
  57.                             For k = 1 To KolSlov
  58.                                 S = S & Predlojenie(k) & " "
  59.                             Next k
  60.                             S = Trim(S)
  61.                             Novoe = True
  62.                             For ii = 1 To PanKol - 1
  63.                                 If Pangramma(ii) = S Then Novoe = False: Exit For
  64.                             Next ii
  65.                             If Novoe Then
  66.                                 For k = 1 To KolSlov
  67.                                     Pangramma(PanKol) = Predlojenie(k)
  68.                                 Next k
  69.                                 Pangramma(PanKol) = S
  70.                                 Exit Do
  71.                             End If
  72.                         End If
  73.                     End If
  74.                     '+++++++++++++++++++++
  75.                    DoEvents  '+++++++++
  76.                    '+++++++++++++++++++++
  77.                Next i
  78.                 'Stop '+++++++++++
  79.            Next j
  80.             kk = kk + 1
  81.             '++++++++++++++++
  82.            If kk Mod 10 = 0 Then
  83.                 Debug.Print kk,
  84.                 For k = 1 To KolSlov
  85.                     Debug.Print Predlojenie(k) & " ";
  86.                 Next k
  87.                 Debug.Print
  88.             End If
  89.             '++++++++++++++++
  90.            SlovoRow(KolSlov) = 0
  91.             'SlovoCol(KolSlov) = 10
  92.            '############################################## ' оптимизация для 33 букв
  93.            SlovoCol(KolSlov) = 5 ' оптимизация для 33 букв
  94.            '############################################## ' оптимизация для 33 букв
  95.            KolSlov = KolSlov - 1
  96.             If KolSlov < 0 Then Exit Do
  97.             OstatokObr = OstatokObrOld(KolSlov)
  98.             '+++++++++++++++ ' Ограничитель итераций
  99.            If kk > 100000 Then End
  100.             '+++++++++++++++
  101.        Loop
  102.     Next PanKol
  103.     '-----------------------------------
  104.    S = ""
  105.     For i = 1 To MaxKolPangramm
  106.         S = S & Pangramma(i) & vbCrLf
  107.     Next
  108.     'MsgBox S
  109.    Debug.Print S
  110. End Sub
  111.  
  112. Function EstVObrazce(Obrazec, Slovo) As Boolean
  113.     Dim i%
  114.     For i = 1 To 33
  115.         If Obrazec(Ch(i)) = False And Slovo(Ch(i)) Then Exit Function
  116.     Next
  117.     EstVObrazce = True
  118. End Function
  119.  
  120. Function ObrazecMinusSlovo(Obrazec, Slovo, Ostatok) As Boolean
  121.     Dim i%
  122.     Ostatok = Obrazec
  123.     For i = 1 To 33
  124.         If Obrazec(i) And Slovo(i) Then Ostatok(i) = False
  125.     Next
  126.     ObrazecMinusSlovo = True
  127. End Function
  128.  
  129. Function NeOstalosBukv(Obrazec) As Boolean
  130.     Dim i%
  131.     For i = 33 To 1 Step -1
  132.         If Obrazec(i) Then Exit Function
  133.     Next
  134.     NeOstalosBukv = True
  135. End Function
  136.  
  137. Sub Cifrogramma(S, Obrazec)
  138.     Dim i%, B$
  139.     For i = 1 To Len(S)
  140.         B = Mid(S, i, 1)
  141.         Select Case B
  142.             Case "ё"
  143.                Obrazec(33) = True
  144.             Case "а" To "я", "ё"
  145.                Obrazec(Asc(B) - 223) = True
  146.         End Select
  147.     Next i
  148. End Sub

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 4.111 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут