Получение конкретных c комбинаций символьного массива

Question

Я новичок в создании собственных алгоритмов, и я застрял, пытаясь создать его для игры, которую создаю. Новый механизм c ищет скрытые слова, которые игрок мог бы ввести в этой игре со словами.

Проблема

Допустим, у меня есть массив символов, содержащий {h, o, t, e , l, b, o, w}. Мне нужно иметь возможность получать комбинации массива, например, где:

1. Каждое слово состоит минимум из 3 букв
2. Все буквы должны использоваться, иначе последовательность недействительна.
3. Без перекрытий

Желаемая последовательность:

1. горячий, локоть
2. хот, луг
3. гостиница, лук
4. отель Bow

Идея состоит в том, что я могу проверить каждую последовательность на допустимые слова с моей базой данных, и в примере последовательности 1 и 3 действительны.

Это простой пример, также можно будет только 1 последовательность, если массив меньше или равен 5 символам, и может быть 3 действительных секретных слова, если массив содержит, скажем, 9 символов.

Добавление другого примера, где массив символов, содержащий {s, i, x, c, a, t, r, o, w}:

Желаемая последовательность:

1. шесть, кошка, ряд
2. шесть, кошка
3. шесть c, atrow
4. sixca, trow
5. sixcat, row
6. sixcatrow

В этом примере только последовательность 1 была действительна после проверки, но она смогла разобрать 3 скрытых слова, которые вознаградят игрока.

Answer 1

Вот псевдокод рекурсивного алгоритма для этой задачи. Основная идея c состоит в том, чтобы разбить проблему на более мелкие задачи, пока вы не придете к базовому условию, которое легко решить (в этом случае либо мы использовали все буквы, либо осталось недостаточно букв, чтобы сделать слово).

// This method "bootstraps" the recursive algorithm
public List<List<String>> findWords(String input) {
    List<List<String>> results = new ArrayList<>();
    findHiddenWordsRecursive(input, new ArrayList(), results);
    return results;
}

private void findHiddenWordsRecursive(String remainingLetters,
                              List<String> partialResult,
                              List<List<String>> results) {

   If there are no remaining letters, then we used all the letters,
   so add the "partial results" to the results, then return.
 
   If there aren't enough letters remaining to make a word, return.

   Loop over all the possible lengths the next word could have.
   (minimum is 3, max is remainingLetters.length).

   For each possible length N:

       If the first N letters of remaining letters is a dictionary word:
           Copy partialResult into a new list called "nextPartialResult".
           Add the word to nextPartialResult.

           Define a string "nextRemainingLetters" which is the substring
           of remainingLetters starting at index N.

           Call findHiddenWordsRecursive(nextRemainingLetters,
                                         nextPartialResult,
                                         results)
}

Answer 2

Эта проблема кажется очень подходящей для рекурсивного решения. Мой подход состоит в том, чтобы определить рекурсию следующим образом:

• Вход: массив символов s и ограничения start и end. Процедура учитывает только часть s от start (включительно) до end (исключая). Это будет обозначено s[start,end).

1. [Инициализация] Определите пустой список последовательностей с именем result.
2. [Рекурсивный регистр] Если end-start >= 6, определите индекс раздела p в диапазоне от start+3 до end-3 (включительно). Рекурсивно собрать последовательности для s[start,p) в список left и аналогично для s[p,end) в список right. Добавьте к result декартово произведение left и right. (То есть для каждой последовательности f, которая является элементом left, и для каждой последовательности g, которая является элементом right, добавьте объединенную последовательность f, g к result.)
3. [Базовый регистр] Если end-start >= 3, добавьте все слово s[start,end) к result. (Необязательно: добавляйте s[start,end), только если это допустимое слово.)
4. Возврат result.

Чтобы сгенерировать весь список, вызовите этот метод с исходным массивом символов и используйте 0 для start и длину массива для end.

Если вас интересуют только допустимые последовательности, вы можете ввести тест словаря в этот процесс. Затем на шаге 3 добавьте s[start,end) к result, только если он прошел проверку. Таким образом, для начала вы возвращаете только действительные последовательности. Это было бы намного эффективнее, особенно если учесть, что недействительные последовательности обычно встречаются гораздо чаще. Обратите внимание, что это откроет возможность того, что метод вернет пустой список, и, следовательно, left и / или right могут быть пустыми на шаге 2; в этом случае декартово произведение также будет пустым.

Answer 3

Это именно то, о чем вы просили. Для простоты я использовал deque .

import java.util.*;

public class Main {
    
    public static HashSet<String> dictionary = new HashSet<String>(); 
    
    public static void test(Deque<String> deque){
        for (Iterator itr = deque.iterator(); itr.hasNext();) { 
            if(!dictionary.contains(itr.next())) return;
        }
        
        System.out.print("Found combination: ");
        for (Iterator itr = deque.iterator(); itr.hasNext();) { 
            System.out.print(itr.next() + " ");
        }
        System.out.println();
    }
    
    public static void checkCombinations(String s, int index, Deque<String> deque){
        int rest = s.length() - index;
        if(rest < 6) {
            deque.addLast(s.substring(index, s.length()));
            test(deque);
            deque.removeLast();
            return;
        }
        for(int i = index + 3; i < s.length() - 2; i++){
            deque.addLast(s.substring(index, i));
            checkCombinations(s, i, deque);
            deque.removeLast();
        }
        deque.addLast(s.substring(index, s.length()));
        test(deque);
        deque.removeLast();
    }
    
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<String>();
        dictionary.add("hotel"); 
        dictionary.add("bow"); 
        dictionary.add("hot"); 
        dictionary.add("elbow");
        checkCombinations("hotelbow", 0, deque);
    }
}

OUTPUT:

Found combination: hot elbow 
Found combination: hotel bow